正题

题面链接:https://www.luogu.com.cn/problem/P5546

---

题目大意

求$n$个串的最长公共子串。

---

解题思路

注意到最长公共子串一定是其中所有的子串，所以我们可以先随意对一个串构建$SAM$然后将信息存在上面即可。

然后每一个其他串都丢到那个$SAM$上跑匹配，每次跑出来的取一个$min$就好了，注意祖先也要附上值。

---

$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; }

总结

以上是生活随笔为你收集整理的P5546-[POI2000]公共串【SAM】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。