CF700E Cool Slogans / YbtOJ「字符串算法」第3章 后缀自动机 G. 重复子串 题解--zhengjun

选出一个字符串序列 s s s，使得对于每一个 s i s_i si​，都是原串的子串，且每个 s i s_i si​ 在 s i − 1 s_{i-1} si−1​ 中都出现过至少两次，求最大的序列长度。

发现其实可以做到让所有选出的字符串都是上一个字符串的后缀，因为如果后面留了一个尾巴，那么前面的字符串把这个尾巴砍了是不影响答案的。

然后发现，其实这个就是 SAM 在 parent 树上的顺序（在 parent 树上，儿子一定是父亲的后缀），那么，只需要从上往下 d p dp dp，记录上一个选择的后缀为 f a fa fa，当前在 u u u，那么就是要判断， s f a s_{fa} sfa​ 是否在 s u s_u su​ 中出现了至少两次，然后我们只需要找到当前的 e n d p o s endpos endpos 集合，查询区间中是否存在一个数即可，这里可以用可持久化线段树合并完成。

#include
using namespace std;typedef long long ll;const int N=4e5+10,M=2e7;char s[N];
int n,ch[N][26],lnk[N],len[N],pos[N],las,root[N],ls[M],rs[M],cnt,tot,cur[N],f[N],st[N],ans;
void update(int &rt,int cur,int l=1,int r=n){
	if(!rt)rt=++cnt;if(l==r)return;int mid=(l+r)>>1;if(cur<=mid)update(ls[rt],cur,l,mid);else update(rs[rt],cur,mid+1,r);
}
void merge(int &x,int y,int l=1,int r=n){
	if(!x||!y)return void(x|=y);ls[++cnt]=ls[x];rs[cnt]=rs[x];x=cnt;if(l==r)return;
	int mid=(l+r)>>1;merge(ls[x],ls[y],l,mid);merge(rs[x],rs[y],mid+1,r);
}
bool query(int rt,int L,int R,int l=1,int r=n){
	if(!rt)return 0;if(L<=l&&r<=R)return 1;int mid=(l+r)>>1;
	if(L<=mid&&query(ls[rt],L,R,l,mid))return 1;if(mid
	int now=++tot,p=las,q,ne;len[now]=len[las]+1;pos[now]=i;while(~p&&!ch[p][c])ch[p][c]=now,p=lnk[p];if(!~p)lnk[now]=0;else{
		q=ch[p][c];if(len[q]==len[p]+1)lnk[now]=q;else{ne=++tot;len[ne]=len[p]+1;memcpy(ch[ne],ch[q],sizeof ch[q]);
			lnk[ne]=lnk[q];pos[ne]=pos[q];while(~p&&ch[p][c]==q)ch[p][c]=ne,p=lnk[p];lnk[now]=lnk[q]=ne;}
	}las=now;update(root[now],i);
}
bool cmp(int x,int y){return len[x]
	scanf("%d%s",&n,s+1);lnk[0]=-1;for(int i=1;i<=n;i++)extend(s[i]-'a',i);for(int i=1;i<=tot;i++)cur[i]=i;
	sort(cur+1,cur+1+tot,cmp);for(int i=tot,u,fa;u=cur[i],fa=lnk[u],i>=1;i--)merge(root[fa],root[u]);
	for(int i=1,u,fa;u=cur[i],fa=lnk[u],i<=tot;ans=max(ans,f[u]),i++)if(!fa)f[u]=1,st[u]=u;
		else if(query(root[st[fa]],pos[u]-len[u]+len[st[fa]],pos[u]-1))f[u]=f[fa]+1,st[u]=u;else f[u]=f[fa],st[u]=st[fa];
	cout< 
有问题请指教，谢谢–zhengjun