题意：求n个字符串的公共子串（n<=10,len(s[i])<=100000）
思路：将第一个字符串建立sam，把其他字符串跑到sam的每个节点的最长匹配长度记录下来。然后对于每个结点取最小，用dp数组记录。但对于每个fa[i],应该dp[fa[i]]=max(dp[fa[i]],dp[i]);
dp数组中最大即为答案。
应该按topu序来的，应该是数据水了。
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=100010; char s[maxn]; struct Suffix_Automaton{ //basic int nxt[maxn*2][26], fa[maxn*2], l[maxn*2]; int last,cnt; int mm[2*maxn]; int dp[2*maxn]; Suffix_Automaton(){ clear(); } void clear(){ last =cnt=1; fa[1]=l[1]=0; memset(nxt[1],0,sizeof nxt[1]); } void init(char *s){ memset(dp,0x3f,sizeof(dp)); while (*s){ add(*s-'a');s++; } } void add(int c){ int p = last; int np = ++cnt; memset(nxt[cnt],0,sizeof nxt[cnt]); l[np] = l[p]+1;last = np; while (p&&!nxt[p][c])nxt[p][c] = np,p = fa[p]; if (!p)fa[np]=1; else{ int q = nxt[p][c]; if (l[q]==l[p]+1)fa[np] =q; else{ int nq = ++ cnt; l[nq] = l[p]+1; memcpy(nxt[nq],nxt[q],sizeof (nxt[q])); fa[nq] =fa[q];fa[np] = fa[q] =nq; while (nxt[p][c]==q)nxt[p][c] =nq,p = fa[p]; } } } void lcs(char *s) { int n=strlen(s); int cur=1; int y=0; memset(mm,0,sizeof(mm)); for(int i=0;i<n;i++) { int c=s[i]-'a'; if(!nxt[cur][c]) { while(cur&&!nxt[cur][c]) cur=fa[cur]; y=l[cur]+1; } else { y++; } cur=cur?nxt[cur][c]:1; if(cur==1) y=0; mm[cur]=max(mm[cur],y); //printf("%d ",mm[cur]); } for(int i=cnt;i>=1;i--) { dp[i]=min(dp[i],mm[i]); //printf("%d ",dp[i]); dp[fa[i]]=max(dp[fa[i]],dp[i]); } } int query() { int ans=0; for(int i=1;i<=cnt;i++) { ans=max(dp[i],ans); } return ans; } }sam; int main() { scanf("%s",s); int n=strlen(s); sam.init(s); int ans; while(~scanf("%s",s)){ sam.lcs(s); } printf("%d ",sam.query()); }