[SPOJ1812]Longest Common Substring II 后缀自动机 多个串的最长公共子串
题目链接：http://www.spoj.com/problems/LCS2/
其实两个串的LCS会了，多个串的LCS也就差不多了。
我们先用一个串建立后缀自动机，然后其它的串在上面跑。跑的时候算出每一个位置能往左扩展的最大长度也就是LCS。
于是对于每一个状态维护mx数组，表示当前串与SAM在此状态的LCS值。对于一个状态取所有mx中的最小值，然后答案就是所有状态最小值中的最大值，证明显然。
两个串的时候不用拿一个状态更新其祖先状态，但是这里需要。SAM是一个DAG图，我们通过l数组来基数排序，从叶子开始一层一层向上更新就行了。实现有点妙，具体看代码。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 char s[250010]; 6 int sz=0,la,rt,len; 7 int l[500010],ch[500010][26],fa[500010],mn[500010]; 8 void Extend(int c){ 9 int end=++sz,tmp=la; 10 l[end]=mn[end]=l[tmp]+1; 11 while(tmp&&!ch[tmp][c]){ 12 ch[tmp][c]=end; 13 tmp=fa[tmp]; 14 } 15 if(!tmp) fa[end]=rt; 16 else{ 17 int ne=ch[tmp][c]; 18 if(l[tmp]+1==l[ne]) fa[end]=ne; 19 else{ 20 int np=++sz; 21 memcpy(ch[np],ch[ne],sizeof(ch[ne])); 22 l[np]=mn[np]=l[tmp]+1; 23 fa[np]=fa[ne]; 24 fa[end]=fa[ne]=np; 25 while(tmp&&ch[tmp][c]==ne){ 26 ch[tmp][c]=np; 27 tmp=fa[tmp]; 28 } 29 } 30 } 31 la=end; 32 } 33 int c[500010],a[500010]; 34 int mx[500010]; 35 void Radixsort(){ 36 for(int i=1;i<=sz;i++) c[l[i]]++; 37 for(int i=1;i<=len;i++) c[i]+=c[i-1]; 38 for(int i=sz;i>=1;i--) a[c[l[i]]--]=i; 39 } 40 void Solve(){ 41 while(scanf("%s",s+1)!=EOF){ 42 int o=rt,lcs=0; 43 for(int i=1;s[i];i++){ 44 int c=s[i]-'a'; 45 if(ch[o][c]){ 46 o=ch[o][c]; 47 mx[o]=max(mx[o],++lcs); 48 } 49 else{ 50 while(o&&!ch[o][c]) o=fa[o]; 51 if(!o){ 52 o=rt; 53 lcs=0; 54 } 55 else{ 56 lcs=l[o]+1; 57 o=ch[o][c]; 58 mx[o]=max(mx[o],lcs); 59 } 60 } 61 } 62 for(int i=sz;i>=1;i--){ 63 int o=a[i]; 64 mn[o]=min(mn[o],mx[o]); 65 if(fa[o]) mx[fa[o]]=max(mx[fa[o]],mx[o]); 66 mx[o]=0; 67 } 68 } 69 } 70 int main(){ 71 rt=la=++sz; 72 scanf("%s",s+1); 73 len=strlen(s+1); 74 for(int i=1;i<=len;i++) Extend(s[i]-'a'); 75 Radixsort(); 76 Solve(); 77 int ans=0; 78 for(int i=1;i<=sz;i++) ans=max(ans,mn[i]); 79 printf("%d ",ans); 80 return 0; 81 }