Bzoj2946 [Poi2000]公共串

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 869 Solved: 380

Description

给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务：

l 读入单词

l 计算最长公共子串的长度

l 输出结果

Input

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

Output

仅一行，一个整数，最长公共子串的长度。

Sample Input

3
abcb
bca
acbc

Sample Output

２

HINT

Source

字符串后缀自动机

用第一个字符串建立后缀自动机，其他字符串在它上面匹配并更新答案。

(同 SPOJ LCS2 没错我就是又敲了一遍模板)

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<vector>
 8 using namespace std;
 9 const int mxn=5010;
10 char s[mxn];
11 struct SAM{
12     int t[mxn][27];
13     int fa[mxn],l[mxn];
14     int S,last,cnt;
15     //
16     int w[mxn];
17     int rk[mxn];
18     int mx[mxn],mn[mxn];
19     //
20     void init(){S=last=cnt=1;return;}
21     void add(int c){
22         int p=last,np=++cnt;last=np;
23         l[np]=l[p]+1;
24         for(;p && !t[p][c];p=fa[p])t[p][c]=np;
25         if(!p)fa[np]=S;
26         else{
27             int q=t[p][c];
28             if(l[q]==l[p]+1)fa[np]=q;
29             else{
30                 int nq=++cnt;
31                 l[nq]=l[p]+1;
32                 memcpy(t[nq],t[q],sizeof t[q]);
33                 fa[nq]=fa[q];
34                 fa[q]=fa[np]=nq;
35                 for(;p && t[p][c]==q;p=fa[p])t[p][c]=nq;
36             }
37         }
38         return;
39     }
40     void st(int len){
41         int i;
42         for(i=1;i<=cnt;i++)++w[l[i]];
43         for(i=1;i<=len;i++)w[i]+=w[i-1];
44         for(i=1;i<=cnt;i++)rk[w[l[i]]--]=i;
45         //
46         for(i=1;i<=cnt;i++)mn[i]=l[i];
47         return;
48     }
49     void solve(){
50         memset(mx,0,sizeof mx);
51         scanf("%s",s+1);
52         int len=strlen(s+1);
53         int p=S,tmp=0;
54         for(int i=1;i<=len;i++){
55             int c=s[i]-'a';
56             if(t[p][c]){tmp++;p=t[p][c];}
57             else{
58                 while(p && !t[p][c])p=fa[p];
59                 if(!p){p=S;tmp=0;}
60                 else{tmp=l[p]+1; p=t[p][c];}
61             }
62             mx[p]=max(mx[p],tmp);
63         }
64         for(int i=cnt;i;i--){//倒序以不断更新fa
65             p=rk[i];
66             mn[p]=min(mn[p],mx[p]);
67             if(fa[p] && mx[fa[p]]<mx[p])mx[fa[p]]=mx[p];
68         }
69     }
70 }sa;
71 int n;
72 int main(){
73     int i,j;
74     scanf("%d",&n);
75     scanf("%s",s+1);
76     int len=strlen(s+1);
77     sa.init();
78     for(i=1;i<=len;i++)
79         sa.add(s[i]-'a');
80     sa.st(len);
81     for(i=2;i<=n;i++) sa.solve();
82     int ans=0;
83     for(i=1;i<=sa.cnt;i++)ans=max(ans,sa.mn[i]);
84     printf("%d
",ans);
85     return 0;
86 }