SPOJ 1812 Longest Common Substring II

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is a bit harder, for some given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.

Example

Input:
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa

Output:
2

題解：
這題走了許多彎路，最後好不容易拍完錯誤，代碼沒有改得精簡.
思路可以參考：
根據上題可以想到，拿每一個串都在A得SAM上跑，然後記錄當前串在SAM得每一個節點的最大值，然後如果是多個串的話
直接記錄最小值即可，最後掃一邊記錄最小值的最大值即可
注意一些細節：
對於沒一個串的匹配，如果當前結點被匹配到了，那麼他的父親結點都可以匹配到，那麼直接拓撲序更新即可，不然就WA#10哦..

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstring>
 5 #define il inline
 6 #define RG register
 7 using namespace std;
 8 const int N=350005;
 9 char s[N];int cur=1,cnt=1,last=1,fa[N],ch[N][27],dis[N],n=0;
10 void build(int c)
11 {
12     last=cur;cur=++cnt;
13     RG int p=last;dis[cur]=++n;
14     for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
15     if(!p)fa[cur]=1;
16     else{
17         int q=ch[p][c];
18         if(dis[q]==dis[p]+1)fa[cur]=q;
19         else{
20             int nt=++cnt;dis[nt]=dis[p]+1;
21             memcpy(ch[nt],ch[q],sizeof(ch[q]));
22             fa[nt]=fa[q];fa[q]=fa[cur]=nt;
23             for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;
24         }
25     }
26 }
27 int id=0,t[N],tot[N],mx[N],sa[N];bool mark[N][15];
28 void FLr()
29 {
30     RG int p=1,l=strlen(s),c,u,len=0;id++;
31     for(RG int i=0;i<l;i++){
32         c=s[i]-'a';
33         u=ch[p][c];
34         if(u){
35             mark[u][id]=true;len++;
36             p=u;
37         }
38         else{
39             while(p && !ch[p][c])p=fa[p];
40             if(p){
41                 mark[ch[p][c]][id]=true;
42                 len=dis[p]+1;
43                 p=ch[p][c];
44             }
45             else p=1,len=0;
46         }
47         if(len>mx[p])mx[p]=len;
48     }
49     for(RG int i=cnt;i;i--){
50         p=sa[i];
51         if(mx[p]<tot[p])tot[p]=mx[p];
52         if(fa[p] && mark[p][id])mx[fa[p]]=dis[fa[p]];
53         mx[p]=0;
54     }
55 }
56 int c[N];
57 void Dfp(){
58     RG int p,i,j;
59     for(i=cnt;i;i--){
60         p=sa[i];
61         for(j=1;j<=id;j++)
62             mark[fa[p]][j]|=mark[p][j];
63     }
64     for(i=1;i<=cnt;i++)
65         for(j=1;j<=id;j++)
66             if(mark[i][j])t[i]++;
67 }
68 int ans=0;
69 void dfs(){
70     for(int i=2;i<=cnt;i++){
71         if(t[i] && tot[i]>ans)ans=tot[i];
72     }
73 }
74 void jip(){
75     RG int i;
76     for(i=1;i<=cnt;i++)c[dis[i]]++;
77     for(i=1;i<=n;i++)c[i]+=c[i-1];
78     for(i=cnt;i;i--)sa[c[dis[i]]--]=i;
79 }
80 void work()
81 {
82     scanf("%s",s);
83     for(RG int i=0,l=strlen(s);i<l;i++)build(s[i]-'a');
84     for(RG int i=1;i<=cnt;i++)tot[i]=N;
85     jip();
86     while(~scanf("%s",s))FLr();
87     Dfp();dfs();
88     printf("%d
",ans);
89 }
90 int main()
91 {
92     freopen("pow.in","r",stdin);
93     freopen("pow.out","w",stdout);
94       work();
95     return 0;
96 }