题目：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 ",ans); return 0; }