首页 > 其他分享 >[十二省联考 2019] 字符串问题

[十二省联考 2019] 字符串问题

时间:2023-08-06 23:11:59浏览次数:46  
标签:类串 SAM int void 2019 hd 字符串 联考 leqslant

题目描述

现有一个字符串 \(S\)。

Tiffany 将从中划出 \(n_a\) 个子串作为 \(A\) 类串,第 \(i\) 个(\(1 \leqslant i \leqslant n_a\))为 \(A_i = S(la_i, ra_i)\)。

类似地,Yazid 将划出 \(n_b\) 个子串作为 \(B\) 类串,第 \(i\) 个(\(1 \leqslant i \leqslant n_b\))为 \(B_i = S(lb_i, rb_i)\)。

现额外给定 \(m\) 组支配关系,每组支配关系 \((x, y)\) 描述了第 \(x\) 个 \(A\) 类串支配 第 \(y\) 个 \(B\) 类串。

求一个长度最大的目标串 \(T\),使得存在一个串 \(T\) 的分割 \(T = t_1+t_2+· · ·+t_k\)(\(k \geqslant 0\))满足:

  • 分割中的每个串 \(t_i\) 均为 \(A\) 类串:即存在一个与其相等的 \(A\) 类串,不妨假设其为 \(t_i = A_{id_i}\)。
  • 对于分割中所有相邻的串 \(t_i, t_{i+1}\)(\(1 \leqslant i < k\)),都有存在一个\(A_{id_i}\) 支配的 \(B\) 类串,使得该 \(B\) 类串为 \(t_{i+1}\) 的前缀。

方便起见,你只需要输出这个最大的长度即可。

特别地,如果存在无限长的目标串(即对于任意一个正整数 \(n\),都存在一个满足限制的长度超过 \(n\) 的串),请输出 \(-1\)。

对于所有测试点中的每一组数据,保证:\(1 \leqslant |S| \leqslant 2 \times 10^5\),\(n_a\), \(n_b \leqslant 2 \times 10^5\),\(m \leqslant 2 \times 10^5\)

考虑建图,对于一个串 \(A\),向他可以到的所有 \(A\) 串连边,跑拓扑,复杂度 \(O(n^2)\)

这是单一串的子串为题,考虑用 SAM 优化建图。对于一个 \(A\) 串连向的 \(B\) 串的所有字符,在 fail 树上的体现就是一个 \(A\) 串连向某一棵子树。可以用倍增找到某一个区间在 SAM 上的节点。

但是要处理若干个区间都对于 SAM 上同一个节点的情况,所以可以先把所有这样的区间用一个 vector 存在对应的节点上,排序后重建 fail 树就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4e5+5;
char s[N];
int l,r,na,nb,m,a[N],b[N],TME,n,al[N],ar[N],bl[N],br[N];
template<int N,int M>struct graph{
	int hd[N],e_num;
	struct edge{
		int v,nxt,w;
	}e[M];
	void add_edge(int u,int v,int w)
	{
		e[++e_num]=(edge){v,hd[u],w};
		hd[u]=e_num;
	}
	void clear()
	{
		e_num=0;
		memset(hd,0,sizeof(hd));
	}
};
struct SAM{
	int tr[N<<1][26],fil[20][N<<2],idx,lst,l[N<<2],in[N<<2],ed[N],q[N<<2];
	LL dp[N<<2];
	graph<N<<2,N<<2> f;
	vector<int>g[N<<1];
	void insert(int s)
	{
		int p=++idx,k=lst;
		lst=p;
		l[p]=l[k]+1;
		ed[l[p]]=p;
		while(k&&!tr[k][s])
			tr[k][s]=p,k=fil[0][k];
		if(!k)
			fil[0][p]=1;
		else
		{
			int q=tr[k][s];
			if(l[q]==l[k]+1)
				fil[0][p]=q;
			else
			{
				int u=++idx;
				memcpy(tr[u],tr[q],sizeof(tr[u]));
				fil[0][u]=fil[0][q],l[u]=l[k]+1;
				fil[0][q]=fil[0][p]=u;
				while(k&&tr[k][s]==q)
					tr[k][s]=u,k=fil[0][k];
			}
		}
	}
	void add_edge(int u,int v,int w)
	{
		f.add_edge(u,v,w);
		in[v]++;
	}
	void init1()
	{
		for(int i=1;i<20;i++)
			for(int j=1;j<=idx;j++)
				fil[i][j]=fil[i-1][fil[i-1][j]];
	}
	void init2()
	{
		for(int i=2;i<=idx;i++)
			add_edge(fil[0][i],i,0);
	}
	int find(int l,int r)
	{
		int k=ed[r];
		for(int i=19;~i;--i)
			if(SAM::l[fil[i][k]]>=r-l+1)
				k=fil[i][k];
		return k;
	}
	void ins(int l,int r)
	{
		int k=ed[r];
		for(int i=19;~i;--i)
			if(SAM::l[fil[i][k]]>=r-l+1)
				k=fil[i][k];
		if(SAM::l[k]!=r-l+1)
			g[k].push_back(r-l+1);
	}
	void init3() 
	{
		for(int i=1;i<=idx;i++)
		{
			sort(g[i].begin(),g[i].end());
			int lst=fil[0][i];
			for(int j=0;j<g[i].size();j++)
			{
				if(j&&g[i][j]==g[i][j-1]&&g[i][j])
					continue;
				int u=++idx;
				fil[0][u]=lst,l[u]=g[i][j];
				lst=u;
			}
			fil[0][i]=lst;
		}
		for(int i=1;i<20;i++)
			for(int j=1;j<=idx;j++)
				fil[i][j]=fil[i-1][fil[i-1][j]];
	}
	LL tuopu()
	{
		int l=1,r=0;
		for(int i=1;i<=idx;i++)
			if(!in[i])
				q[++r]=i;
		while(l<=r)
		{
			for(int i=f.hd[q[l]];i;i=f.e[i].nxt)
			{
				--in[f.e[i].v];
				if(!in[f.e[i].v])
					q[++r]=f.e[i].v;
				dp[f.e[i].v]=max(dp[f.e[i].v],dp[q[l]]+f.e[i].w);
			}
			++l;
		}
		for(int i=1;i<=idx;i++)
			if(in[i])
				return -1;
		return dp[idx+1];
	}
	void clear()
	{
		memset(tr,0,sizeof(tr));
		for(int i=1;i<=idx;i++)
			g[i].clear();
		memset(dp,0,sizeof(dp));
		f.clear();
		memset(in,0,sizeof(in));
		memset(fil,0,sizeof(fil));
		lst=idx=1;
	}
}p;
int main()
{
	//freopen("3.in","r",stdin);
	scanf("%d",&TME);
	while(TME--)
	{
		p.clear();
		scanf("%s",s+1),n=strlen(s+1);
		for(int i=n;i>=1;i--)
			p.insert(s[i]-'a');
		p.init1(); 
		scanf("%d",&na);
		for(int i=1;i<=na;i++) 
			scanf("%d%d",al+i,ar+i),p.ins(n-ar[i]+1,n-al[i]+1);
		scanf("%d",&nb);
		for(int i=1;i<=nb;i++)
			scanf("%d%d",bl+i,br+i),p.ins(n-br[i]+1,n-bl[i]+1);
		p.init3();
		p.init1();
		for(int i=1;i<=na;i++)
			a[i]=p.find(n-ar[i]+1,n-al[i]+1);
		for(int i=1;i<=nb;i++)
			b[i]=p.find(n-br[i]+1,n-bl[i]+1);
		scanf("%d",&m);
		for(int i=1,x,y;i<=m;i++)
			scanf("%d%d",&x,&y),p.add_edge(a[x],b[y],p.l[a[x]]);
		for(int i=1;i<=na;i++)
			p.add_edge(a[i],p.idx+1,p.l[a[i]]);
		p.init2();
		printf("%lld\n",p.tuopu());
	}
	return 0;
}

标签:类串,SAM,int,void,2019,hd,字符串,联考,leqslant
From: https://www.cnblogs.com/mekoszc/p/17610316.html

相关文章

  • IMOSL2019 C3~C9
    C3有一个很妙的做法。考虑把整个过程倒过来看。一开始,有一个指针在位置\(0\),所有硬币都是T。每次,可以把指针右移一位,使得移动后的指针指向一个T,之后要把这个T变为H可以把指针左移一位,使得移动后的指针指向一个H,之后要把这个H变为T考虑左移/右移操作形成的连续段......
  • 字符串相关
    KMP下标从\(1\)开始求border:intkmp[N];voidKMP(char*s,intlen){ for(inti=2,j=0;i<=len;i++){ while(j&&s[i]!=s[j+1])j=kmp[j]; if(s[i]==s[j+1])j++; kmp[i]=j; }}intlen;chars[N];intmain(){ scanf("%s",s+1),len=strlen(s+1)......
  • 请输入一个字符串 由此可以得出这个字符串大写字母.小写字母.数字.符号的个数
    importjava.util.Scanner;publicclassDemo02{  publicstaticvoidmain(String[]args){    System.out.println("请输入一个字符串:");    Stringcc=newScanner(System.in).nextLine();    char[]arr=cc.toCharArray();    intc......
  • 【JavaScript08】字符串基本操作
    字符串基本方法,本文只对部分方法做了说明其它更多参考菜鸟教程https://www.runoob.com/jsref/jsref-obj-string.htmls.split()字符串切割s.substr(start,len)字符串切割,从start开始切,切len个字符;如果len不给,直接切到最后s.substring(start,end)字符串切割,从st......
  • 【JavaScript09】模板字符串(Template Strings)
    前言JavaScript在ES6新增了模板字符串(TemplateStrings)语法,其作用是可以在字符串中换行,以及将变量和表达式插入字符串。模板字符串模板字面量使用反引号(``)而不是单引号('')或双引号("")来定义字符串示例:letuser="xwl";letage=20;letx=`myname......
  • zabbix触发器标签提取监控项子字符串功能实现对应告警恢复
    0实验环境zabbix6.01监控项1.1监控项设置通过zabbixagent自定义监控项,读取某文件内容模拟日志/trap告警,测试获取触发器标签中提取子字符串功能,以及相同标签的触发器自动恢复功能。1.2手工运行手动触发之后,模拟产生如下日志数据,意为集群中node-01主机离线。07:28:29......
  • 代码随想录算法训练营第七天|力扣334.反转字符串、力扣541.反转字符串II、剑指offer05
    字符串反转字符串(力扣344.)如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。毕竟面试官一定不是考察你对库函数的熟悉程度,如果使用python和java的同学更需要注意这一点,因为python、java提供的库函数十分丰富。如果库函数仅仅是解题过程中的一小部分,并且......
  • 前端学习笔记202306学习笔记第三十八天-Es6-字符串的解构赋值1
      ......
  • 【ACM专项练习#02】输入整行字符串、输入值到vector、取输入整数的每一位
    输入整行字符串平均绩点题目描述每门课的成绩分为A、B、C、D、F五个等级,为了计算平均绩点,规定A、B、C、D、F分别代表4分、3分、2分、1分、0分。输入有多组测试样例。每组输入数据占一行,由一个或多个大写字母组成,字母之间由空格分隔。输出每组输出结果占一行。如果输入的大......
  • 11_字符串操作函数
    字符串操作函数以str开头的函数都是字符串操作函数都是遇到'\0'结束操作strlen测量字符串长度#include<string.h>size_tstrlen(constchar*s);s:需要测量字符串的首元素地址charstr[128]="hello";strlen(str);//5strcpy字符串拷贝函数#include<string.h>......