SPOJ LCS Longest Common Substring （后缀自动机模板题）
题意：
给出2个字符串(2.5E5)，问最长公共子串的长度。
思路：
拿一个串建SAM
由于SAM上的任何一个状态，都对应一个或者若干个子串，然后拿另一个串在SAM上面跑就行了
20171110UPdate:我好像说得太简略了。。
参考clj的冬令营讲稿：
* 给两个长度小于100000的字符串A和B，求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM * 对于SAM的每个状态s，令r为Right(s)中任意的一个元素，它代表的是结束位置在r的，长度在[Min(s),Max(s)]之间的所有子串。 * 我们不妨对状态s，求出所有B的子串中，从任意r开始往前能匹配的最大长度L，那么min(L,Max(s))就可以更新答案了。 * 我们考虑用_SAM_读入字符串_B_。 * **令当前状态为_s_，同时最大匹配长度为_len _Ê我们读入字符_x_。如果_s_有标号为_x_的边，** * **那么_s=trans(s,x),len = len+1 _Ê否则我们找到_s_的第一个祖先_a_，它有标号为_x_的边，令** * **_s=trans(a,x),len=Max(a)+1__。 _Ê如果没有这样的祖先，那么令_s=root,len=0_。** * 在过程中更新状态的最大匹配长度
唯一不显然的地方在于，为什么当失配时，我们是沿着parent树向上找。
考虑如下例子：
我们知道，parent树，或者叫后缀链树，一个状态S指向的是，总起点开始到S的子串的后缀中，长度最长的后缀，满足该后缀所对应的某个状态Q(对应的意思是说，从初始状态到状态Q表示的子串恰好是该后缀)的right集合和状态S的集合不相等。
假设我们目前匹配到的状态表示的子串是abcbc,然后下一位要匹配的字母是b，而状态abcbc没有通过b转移的边（这些图上没有,我懒得画了orz)
这个时候考虑回退...对于abcbc的后缀，bcbc,cbc和abcbc面临的情况是一样的，因为bcbc,cbc,abcbc三个字符串的right集合相同，也就是出现的位置完全相同，那么既然abcbc没有通过b转移的边，bcbc,cbc也一定没有通过b转移的边。
这时候考虑转移到abcbc的par状态，也就是表示子串bc的状态，原因是bc的right集合和abcbc的right集合不同，更准确得说，bc的right集合是包含abcbc的right集合的。
而bc在之前匹配abcbc的时候，已经匹配过了，也就是说bc一定是可以匹配的，
如果此时bc有一条通过b转移的边，此时匹配的长度就变成了bc对应的状态所对应的max再+1
老年人的第一个SAM
关于SAM的笔记之后补。
用了动态的写法.
/* ***********************************************
Author :111qqz
Created Time :2017年11月03日 星期五 18时20分42秒hongchenzuoban
File Name :2774_SAM.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lnxt l,m,rt<<1
6#define rnxt m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=3E5;
7struct SAM
8{
9 struct node
10 {
11 node *nxt[26],*fa;int len;
12 node(int M) {len=M;fa=0;memset(nxt,0,sizeof(nxt));}
13 };
14 typedef node* P_node;
15 P_node ro,lst;
16 SAM() {ro=new node(0);lst=ro;}
17 void Insert(char ch)
18 {
19 int ID=ch-'a';P_node p=lst,np=new node(lst->len+1);
20 while (p&&!p->nxt[ID]) p->nxt[ID]=np,p=p->fa;
21 if (!p) np->fa=ro; else
22 {
23 P_node q=p->nxt[ID];
24 if (p->len+1==q->len) np->fa=q; else
25 {
26 P_node nq=new node(p->len+1);
27 memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
28 nq->fa=q->fa;q->fa=nq;np->fa=nq;
29 while (p&&p->nxt[ID]==q) p->nxt[ID]=nq,p=p->fa;
30 }
31 }
32 lst=np;
33 }
34 void make_SAM(char *s) {for (int i=0; s[i]!='\0';i++) Insert(s[i]);}
35 int LCS(char *s) //求此后缀自动机对应字符串与s的LCS
36 {
37 int ans=0,len=0;P_node p=ro;
38 for (int i=0;s[i]!='\0';i++)
39 {
40 int ID=s[i]-'a';
41 if (p->nxt[ID]) p=p->nxt[ID],len++; else
42 {
43 while (p&&!p->nxt[ID]) p=p->fa;
44 if (!p) p=ro,len=0; else len=p->len+1,p=p->nxt[ID];
45 }
46 ans=max(ans,len); //从所有len中刷出最优解
47 }
48 return ans;
49 }
50};
51SAM sam;
52char A[N],B[N];
53int main()
54{
55 #ifndef ONLINE_JUDGE
56 freopen("./in.txt","r",stdin);
57 #endif
58 scanf("%s %s",A,B);
59// cout<<A<<endl;
60// cout<<B<<endl;
61 sam.make_SAM(A);
62 int ans = sam.LCS(B);
63 printf("%d\n",ans);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
不过还是比较喜欢写静态的？
参考了zqc大爷的代码风格：
/* ***********************************************
Author :111qqz
Created Time :2017年11月03日 星期五 18时20分42秒
File Name :2774_SAM.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lnxt l,m,rt<<1
6#define rnxt m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
const int maxn = 5E5;
1struct node{
2 node*nxt[26],*fail;
3 LL len,cnt;
4 int ind;
5 int occ;
6};
7struct SAM{
8 node no[maxn];
9 node*root;
10 int cnt;
11 node*newnode(){
12 return &no[cnt++];
13 }
14 SAM(){
15 cnt = 0;
16 root = newnode();
17 }
18 node*add(int c,node*p){
19 node*cur = newnode();
20 cur->len = p->len+1;
21 while(p&&!p->nxt[c]){
22 p->nxt[c] = cur;
23 p = p->fail;
24 }
25 if(!p){
26 cur->fail = root;
27 return cur;
28 }
29 node*q = p->nxt[c];
30 if(p->len+1==q->len){
31 cur->fail = q;
32 }else{
33 node*nq = newnode();
34 *nq = *q;
35 q->fail = cur->fail = nq;
36 nq->len = p->len+1;
37 while(p&&p->nxt[c]==q){
38 p->nxt[c] = nq;
39 p = p->fail;
40 }
41 }
42 return cur;
43 }
44 int LCS(string s)
45 {
46// cout<<"S:"<<s<<endl;
47 int ans=0,len=0;
48 node *p=root;
49 for ( auto i:s)
50 {
51 int ID = i-'a';
52 //cout<<"id:"<<ID<<" s[i]:"<<i<<" i:"<<i<<endl;
53 if (p->nxt[ID]) p=p->nxt[ID],len++;
54 else
55 {
56 while (p&&!p->nxt[ID]) p=p->fail;
57 if (!p) p=root,len=0;else len=p->len+1,p=p->nxt[ID];
58 }
59 ans = max(ans,len);
60 }
61 return ans;
62 }
63};
64SAM sam;
65string A,B;
66int main()
67{
68 #ifndef ONLINE_JUDGE
69// freopen("./in.txt","r",stdin);
70 #endif
71 node *cur =sam.root;
72 cin>>A>>B;
73 for ( auto i:A) cur = sam.add(i-'a',cur);
74 int ans = sam.LCS(B);
75 printf("%d\n",ans);
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}
/* ***********************************************
Author :111qqz
Created Time :2017年11月15日 星期三 19时06分15秒
File Name :SAM.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6#define MAXALP 30
7const int N=5E5+7;
8struct SAM
9{
10 struct state
11 {
12 int len, link, nxt[MAXALP];
13 int leftmost; //某个状态的right集合中r值最小的
14 int rightmost;//某个状态的right集合的r的最大值
15 int Right; //right集合大小
16 };
17 state st[N*2];
18 char S[N];
19 int sz, last,rt;
20 char s[N];
21 int cnt[2*N],rk[2*N];//for radix sort
22 void init()
23 {
24 sz = 0;
25 last = rt = ++sz;
26 st[1].len = 0;
27 st[1].link=-1;
28 st[1].rightmost=0;
29 ms(st[1].nxt,-1);
30 }
31 void extend(int c,int head)
32 {
33 int cur = ++sz;
34 st[cur].len = st[last].len + 1;
35 st[cur].leftmost = st[cur].rightmost = head;
36 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
37 int p;
38 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
39 st[p].nxt[c] = cur;
40 if (p == -1) {
41 st[cur].link = rt;
42 } else {
43 int q = st[p].nxt[c];
44 if (st[p].len + 1 == st[q].len) {
1 st[cur].link = q;
2 } else {
3 int clone = ++sz ;
4 st[clone].len = st[p].len + 1;
5 st[clone].link = st[q].link;
6 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
7 st[clone].leftmost = st[q].leftmost;
8 st[clone].rightmost = st[q].rightmost;
9 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
10 st[p].nxt[c] = clone;
11 st[q].link = st[cur].link = clone;
12 }
13 }
14 last = cur;
15 }
16 void topo()
17 {
18 ms(cnt,0);
19 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
20 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
21 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
22 }
23 void pre() //跑拓扑序，预处理一些东西
24 {
25 for ( int i = sz ; i >= 2 ; i--)
26 {
27 int v = rk[i];
28 int fa = st[v].link;
29 if (fa==-1) continue;
30 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
31 st[fa].Right += st[v].Right;
32 }
33 }
34 void solve()
35 {
1 LL ans = 0 ;
2 for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
3 ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
4 printf("%lld\n",ans);
5 }
6 int LCS(char *s)
7 {
8 int ans = 0,len = 0 ;
9 int p = rt;
10 for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
11 {
12 int ID = s[i]-'a';
13 if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
14 else
15 {
16 while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
17 if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
18 }
19 // printf("len:%d\n",len);
20 ans = max(ans,len);
21 }
22 return ans;
23 }
24}A;
25char B[N];
26int main()
27{
28#ifndef ONLINE_JUDGE
29 freopen("./in.txt","r",stdin);
30#endif
31 A.init();
32 cin>>A.S>>B;
33 for ( int i = 0 ,len=strlen(A.S) ; i < len ; i++) A.extend(A.S[i]-'a',i);
34 int ans = A.LCS(B);
35 cout<<ans<<endl;
36#ifndef ONLINE_JUDGE
37 fclose(stdin);
38#endif
39 return 0;
40}