正题
题面链接:https://www.luogu.com.cn/problem/P5546
题目大意
求 n n n个串的最长公共子串。
解题思路
注意到最长公共子串一定是其中所有的子串,所以我们可以先随意对一个串构建 S A M SAM SAM然后将信息存在上面即可。
然后每一个其他串都丢到那个 S A M SAM SAM上跑匹配,每次跑出来的取一个 m i n min min就好了,注意祖先也要附上值。
c o d e code code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4100;
int n,cnt,last,f[N],g[N],ans,c[N],rk[N];
int ch[N][26],fa[N],len[N];
char s[N];
void Ins(int c){
int p=last;int np=last=++cnt;
len[np]=len[p]+1;
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
if(!p)fa[np]=1;
else{
int q=ch[p][c];
if(len[p]+1==len[q])fa[np]=q;
else{
int nq=++cnt;len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[nq]));
fa[nq]=fa[q];fa[np]=fa[q]=nq;
for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
}
return;
}
void solve(){
scanf("%s",s);int ls=strlen(s);
memset(f,0,sizeof(f));
int x=1,l=0;
for(int i=0;i<ls;i++){
int c=s[i]-'a';
if(ch[x][c])x=ch[x][c],l++;
else{
while(x&&!ch[x][c])x=fa[x];
if(!x)x=1,l=0;
else l=len[x]+1,x=ch[x][c];
}
f[x]=max(f[x],l);
}
for(int i=cnt;i>=1;i--)f[fa[rk[i]]]=max(f[fa[rk[i]]],f[rk[i]]);
for(int i=1;i<=cnt;i++)g[i]=min(g[i],f[i]);
return;
}
int main()
{
scanf("%d",&n);last=cnt=1;
scanf("%s",s);int l=strlen(s);
for(int i=0;i<l;i++)Ins(s[i]-'a');
for(int i=1;i<=cnt;i++)g[i]=len[i];
for(int i=1;i<=cnt;i++)c[len[i]]++;
for(int i=1;i<=l;i++)c[i]+=c[i-1];
for(int i=1;i<=cnt;i++)rk[c[len[i]]--]=i;
for(int i=2;i<=n;i++)solve();ans=0;
for(int i=1;i<=cnt;i++)ans=max(ans,g[i]);
printf("%d",ans);
return 0;
}