bzoj 2946 [Poi2000]公共串——后缀自动机

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2946

对每个串都建一个后缀自动机，然后 dfs 其中一个自动机，记录同步的话在别的自动机上走到哪些点了；只要有一个自动机上走不下去了，就都走不下去了。每走到一个新地方就更新一下 ans 。

或者像网上的其他题解一样，对一个串建一个后缀自动机，其他串跑一遍并在 parent 树上更新了之后得知自动机的每个点在当前串上能匹配的长度，最后对自动机上每个点的答案取 max 。不过没写这个。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005,M=N<<1,K=30,tN=10;
char s[N]; int T,lst,cnt,go[tN][M][K],fa[tN][M],l[tN][M],p[M][tN],ans;
int Mx(int a,int b){return a>b?a:b;}
void add(int x,int w)
{int p=lst,np=++cnt;lst=np;l[x][np]=l[x][p]+1;for(;p&&!go[x][p][w];p=fa[x][p])go[x][p][w]=np;if(!p)fa[x][np]=1;else{int q=go[x][p][w];if(l[x][q]==l[x][p]+1)fa[x][np]=q;else{int nq=++cnt;l[x][nq]=l[x][p]+1;fa[x][nq]=fa[x][q];fa[x][q]=nq;fa[x][np]=nq;memcpy(go[x][nq],go[x][q],sizeof go[x][q]);for(;go[x][p][w]==q;p=fa[x][p])go[x][p][w]=nq;}}
}
void dfs(int cr,int len)
{ans=Mx(ans,len);//
  for(int w=1;w<=26;w++)if(go[1][cr][w]){bool flag=1; int d=go[1][cr][w];for(int t=2;t<=T;t++)if(!go[t][p[cr][t]][w]){flag=0;break;}else p[d][t]=go[t][p[cr][t]][w];if(!flag)continue;dfs(d,len+1);}
}
int main()
{scanf("%d",&T);for(int t=1;t<=T;t++){scanf("%s",s);int d=strlen(s);lst=cnt=1;for(int i=0;i<d;i++)add(t,s[i]-'a'+1);}for(int t=1;t<=T;t++)p[1][t]=1;dfs(1,0); printf("%d\n",ans);return 0;
}