spoj 1812 LCS2（SAM+DP）

【题目链接】

　　http://www.spoj.com/problems/LCS2/en/

【题意】

　　求若干个串的最长公共子串。

【思路】

　　SAM+DP

　　先拿个串建个SAM，然后用后面的串匹配，每次将所有的匹配长度记录在状态上取min，然后对所有状态取max即答案。

　　需要更新fa，因为fa[p]一定比p更优，但匹配的时候可能只更新了p而没有更新fa[p]，所以还需要递推一边。

　　注意mn[p]初始化为l[p]

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 const int N = 5*1e5+10;
 6 
 7 char s[N];
 8 int sz,last,root,l[N],ch[N][26],fa[N],mn[N],mx[N];
 9 int b[N],cnt[N];
10 void add(int x) {
11     int c=s[x]-'a';
12     int p=last,np=++sz; last=np; 
13     l[np]=mn[np]=x+1;
14     for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
15     if(!p) fa[np]=root;
16     else {
17         int q=ch[p][c];
18         if(l[p]+1==l[q]) fa[np]=q;
19         else {
20             int nq=++sz; l[nq]=mn[nq]=l[p]+1;
21             memcpy(ch[nq],ch[q],sizeof(ch[q]));
22             fa[nq]=fa[q];
23             fa[np]=fa[q]=nq;
24             for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
25         }
26     }
27 }
28 
29 int main() {
30     root=last=++sz;
31     scanf("%s",s);
32     int len=strlen(s);
33     for(int i=0;i<len;i++) add(i);
34     for(int i=1;i<=sz;i++) cnt[l[i]]++;
35     for(int i=1;i<=len;i++) cnt[i]+=cnt[i-1];
36     for(int i=1;i<=sz;i++) b[cnt[l[i]]--]=i;
37     while(scanf("%s",s)==1) {
38         int p=root; len=0;
39         for(int i=0;s[i];i++) {
40             int c=s[i]-'a';
41             if(ch[p][c]) { len++; p=ch[p][c]; }
42             else {
43                 while(p&&!ch[p][c]) p=fa[p];
44                 if(!p) { len=0; p=root; }
45                 else { len=l[p]+1; p=ch[p][c]; }
46             }
47             if(len>mx[p]) mx[p]=len;
48         }
49         for(int i=sz;i;i--) {
50             p=b[i];
51             if(mx[p]<mn[p]) mn[p]=mx[p];
52             if(fa[p] && mx[fa[p]]<mx[p]) mx[fa[p]]=mx[p];
53             mx[p]=0;
54         }
55     }
56     int ans=0;
57     for(int i=1;i<=sz;i++)
58         if(mn[i]>ans) ans=mn[i];
59     printf("%d",ans);
60     return 0;
61 }