Description

给定一个串 \(S\),求一个序列 \(a_i\),满足 \(a_i\) 是原串的子串,且 \(a_i\) 在 \(a_{i-1}\) 中至少出现两次,求这个序列的最大的长度

题面

Solution

根据后缀自动机的性质可以做,首先建出 \(parent\) 树,然后满足条件的序列一定是树上的一条链去掉一些节点

然后就是需要满足出现两次的要求了:

因为是祖先关系,所以至少出现了一次,设 \(pos[i]\) 表示节点 \(i\) 所接受的子串都是以原串中 \(pos[i]\) 这个位置结尾的

另外一次我们就找到这个子串在原串中所代表的区间:\([pos[x]-(len[x]-len[fa[x]]),pos[x]]\),如果这个节点在某个儿子节点所代表的区间中出现了两次,那么就符合要求了

我们用线段树维护 \(pos\) 集合就行了,我们从下往上线段树合并就行了

#include<bits/stdc++.h>

using namespace std;

const int N=4e5+10;

int n,ch[N][26],fa[N],cur=1,cnt=1,len[N],b[N],f[N],ans=0;char s[N];

int pos[N],rt[N],ls[N*30],rs[N*30],tt=0,head[N],nxt[N],to[N],num=0;

inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}

inline void Modify(int &x,int l,int r,int sa){

	if(!x)x=++tt;

	if(l==r)return ;

	int mid=(l+r)>>1;

	if(sa<=mid)Modify(ls[x],l,mid,sa);

	else Modify(rs[x],mid+1,r,sa);

}

inline void ins(int c){

	int p=cur;cur=++cnt;len[cur]=len[p]+1;

	for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;

	if(!p)fa[cur]=1;

	else{

		int q=ch[p][c];

		if(len[p]+1==len[q])fa[cur]=q;

		else{

			int nt=++cnt;len[nt]=len[p]+1;

			memcpy(ch[nt],ch[q],sizeof(ch[nt]));

			fa[nt]=fa[q];fa[q]=fa[cur]=nt;

			for(;p && ch[p][c]==q;p=fa[p])ch[p][c]=nt;

		}

	}

}

inline int merge(int x,int y){

	if(!x || !y)return x+y;

	int c=++tt;

	ls[c]=merge(ls[x],ls[y]);

	rs[c]=merge(rs[x],rs[y]);

	return c;

}

inline void dfs(int x){

	for(int i=head[x];i;i=nxt[i]){

		dfs(to[i]),rt[x]=merge(rt[x],rt[to[i]]);

		if(!pos[x])pos[x]=pos[to[i]];

	}

}

inline bool qry(int x,int l,int r,int sa,int se){

	if(!x)return false;

	if(sa<=l && r<=se)return true;

	int mid=(l+r)>>1;

	if(se<=mid)return qry(ls[x],l,mid,sa,se);

	if(sa>mid)return qry(rs[x],mid+1,r,sa,se);

	return qry(ls[x],l,mid,sa,mid)|qry(rs[x],mid+1,r,mid+1,se);

}

inline void dfs1(int x){

	for(int i=head[x],t,u;i;i=nxt[i]){

		u=to[i];

		t=qry(rt[b[x]],1,n,pos[u]-len[u]+len[b[x]],pos[u]-1);

		if(t)f[u]=f[x]+1,b[u]=u;

		else f[u]=f[x],b[u]=b[x];

		dfs1(u);

	}

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

  scanf("%d%s",&n,s+1);

  for(int i=1;i<=n;i++)

	  ins(s[i]-'a'),pos[cur]=i,Modify(rt[cur],1,n,i);

  for(int i=2;i<=cnt;i++)link(fa[i],i);

  dfs(1);

  for(int i=head[1];i;i=nxt[i])b[to[i]]=to[i],f[to[i]]=1,dfs1(to[i]);

  for(int i=2;i<=cnt;i++)ans=max(ans,f[i]);

  printf("%d\n",ans);

  return 0;

}