SPOJ 1811 LCS 后缀自动机

题意：

给两个字符串A、B求他们的最长公共字串。

题解：

后缀自动机啊。你怎么这么恶心这么神啊。。。

必然还是我太弱了。。

第一次搞，参考了别人的代码。

将A建立成后缀自动机，后缀自动机的任意一个节点都表示若干个A的字串，让B在后缀自动机上匹配，不能匹配就沿着f指针转移就是了。

在这个过程中维护自动机的一个节点对应的right集合的最大匹配长度。取最大值就是答案。

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 
 7 #define N 500500
 8 
 9 using namespace std;
10 
11 struct SAM
12 {
13     SAM *son[26],*f;
14     int l;
15 }sam[N],*head,*last;
16 
17 char str[N],b[N];
18 int cnt,ans,len;
19 
20 inline void add(int x)
21 {
22     SAM *p=&sam[++cnt],*bj=last;
23     p->l=last->l+1; last=p;
24     for(;bj&&!bj->son[x];bj=bj->f) bj->son[x]=p;
25     if(!bj) p->f=head;
26     else if(bj->l+1==bj->son[x]->l) p->f=bj->son[x];
27     else
28     {
29         SAM *r=&sam[++cnt],*q=bj->son[x];
30         *r=*q; r->l=bj->l+1; 
31         p->f=q->f=r;
32         for(;bj&&bj->son[x]==q;bj=bj->f) bj->son[x]=r;
33     }
34 }
35 
36 inline void read()
37 {
38     scanf("%s%s",str,b);
39     len=strlen(str);
40     head=last=&sam[cnt=0];
41     for(int i=0;i<len;i++) add(str[i]-'a');
42     len=strlen(b);
43     for(int i=0;i<len;i++) b[i]-='a';
44 }
45 
46 inline void go()
47 {
48     last=head;
49     int res=0;
50     for(int i=0;i<len;i++)
51     {
52         if(last->son[b[i]]) res++,last=last->son[b[i]];
53         else
54         {
55             for(;last&&!last->son[b[i]];last=last->f);
56             if(!last) last=head,res=0;
57             else res=last->l+1,last=last->son[b[i]];
58         }
59         ans=max(ans,res);
60     }
61     printf("%d\n",ans);
62 }
63 
64 int main()
65 {
66     read(),go();
67     return 0;
68 }