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的笔记之后补。
用了动态的写法.
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月03日 星期五 18时20分42秒hongchenzuoban
4File Name :2774_SAM.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lnxt l,m,rt<<1
12#define rnxt m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=3E5;
24struct SAM
25{
26 struct node
27 {
28 node *nxt[26],*fa;int len;
29 node(int M) {len=M;fa=0;memset(nxt,0,sizeof(nxt));}
30 };
31 typedef node* P_node;
32 P_node ro,lst;
33 SAM() {ro=new node(0);lst=ro;}
34 void Insert(char ch)
35 {
36 int ID=ch-'a';P_node p=lst,np=new node(lst->len+1);
37 while (p&&!p->nxt[ID]) p->nxt[ID]=np,p=p->fa;
38 if (!p) np->fa=ro; else
39 {
40 P_node q=p->nxt[ID];
41 if (p->len+1==q->len) np->fa=q; else
42 {
43 P_node nq=new node(p->len+1);
44 memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
45 nq->fa=q->fa;q->fa=nq;np->fa=nq;
46 while (p&&p->nxt[ID]==q) p->nxt[ID]=nq,p=p->fa;
47 }
48 }
49 lst=np;
50 }
51 void make_SAM(char *s) {for (int i=0; s[i]!='\0';i++) Insert(s[i]);}
52 int LCS(char *s) //求此后缀自动机对应字符串与s的LCS
53 {
54 int ans=0,len=0;P_node p=ro;
55 for (int i=0;s[i]!='\0';i++)
56 {
57 int ID=s[i]-'a';
58 if (p->nxt[ID]) p=p->nxt[ID],len++; else
59 {
60 while (p&&!p->nxt[ID]) p=p->fa;
61 if (!p) p=ro,len=0; else len=p->len+1,p=p->nxt[ID];
62 }
63 ans=max(ans,len); //从所有len中刷出最优解
64 }
65 return ans;
66 }
67};
68SAM sam;
69char A[N],B[N];
70int main()
71{
72 #ifndef ONLINE_JUDGE
73 freopen("./in.txt","r",stdin);
74 #endif
75 scanf("%s %s",A,B);
76// cout<<A<<endl;
77// cout<<B<<endl;
78 sam.make_SAM(A);
79 int ans = sam.LCS(B);
80 printf("%d\n",ans);
81
82 #ifndef ONLINE_JUDGE
83 fclose(stdin);
84 #endif
85 return 0;
86}
不过还是比较喜欢写静态的？
参考了zqc大爷的代码风格：
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月03日 星期五 18时20分42秒
4File Name :2774_SAM.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lnxt l,m,rt<<1
12#define rnxt m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23
24const int maxn = 5E5;
25
26struct node{
27 node*nxt[26],*fail;
28 LL len,cnt;
29 int ind;
30 int occ;
31};
32struct SAM{
33 node no[maxn];
34 node*root;
35 int cnt;
36 node*newnode(){
37 return &no[cnt++];
38 }
39 SAM(){
40 cnt = 0;
41 root = newnode();
42 }
43 node*add(int c,node*p){
44 node*cur = newnode();
45 cur->len = p->len+1;
46 while(p&&!p->nxt[c]){
47 p->nxt[c] = cur;
48 p = p->fail;
49 }
50 if(!p){
51 cur->fail = root;
52 return cur;
53 }
54 node*q = p->nxt[c];
55 if(p->len+1==q->len){
56 cur->fail = q;
57 }else{
58 node*nq = newnode();
59 *nq = *q;
60 q->fail = cur->fail = nq;
61 nq->len = p->len+1;
62 while(p&&p->nxt[c]==q){
63 p->nxt[c] = nq;
64 p = p->fail;
65 }
66 }
67 return cur;
68 }
69 int LCS(string s)
70 {
71// cout<<"S:"<<s<<endl;
72 int ans=0,len=0;
73 node *p=root;
74 for ( auto i:s)
75 {
76 int ID = i-'a';
77 //cout<<"id:"<<ID<<" s[i]:"<<i<<" i:"<<i<<endl;
78 if (p->nxt[ID]) p=p->nxt[ID],len++;
79 else
80 {
81 while (p&&!p->nxt[ID]) p=p->fail;
82 if (!p) p=root,len=0;else len=p->len+1,p=p->nxt[ID];
83 }
84 ans = max(ans,len);
85 }
86 return ans;
87 }
88};
89SAM sam;
90string A,B;
91int main()
92{
93 #ifndef ONLINE_JUDGE
94// freopen("./in.txt","r",stdin);
95 #endif
96 node *cur =sam.root;
97 cin>>A>>B;
98 for ( auto i:A) cur = sam.add(i-'a',cur);
99 int ans = sam.LCS(B);
100 printf("%d\n",ans);
101
102 #ifndef ONLINE_JUDGE
103 fclose(stdin);
104 #endif
105 return 0;
106}
107
108
109
110
111
112
113
114
115/* ***********************************************
116Author :111qqz
117Created Time :2017年11月15日 星期三 19时06分15秒
118File Name :SAM.cpp
119************************************************ */
120
121#include <bits/stdc++.h>
122#define PB push_back
123#define fst first
124#define sec second
125#define lson l,m,rt<<1
126#define rson m+1,r,rt<<1|1
127#define ms(a,x) memset(a,x,sizeof(a))
128typedef long long LL;
129#define pi pair < int ,int >
130#define MP make_pair
131
132using namespace std;
133const double eps = 1E-8;
134const int dx4[4]={1,0,0,-1};
135const int dy4[4]={0,-1,1,0};
136const int inf = 0x3f3f3f3f;
137#define MAXALP 30
138const int N=5E5+7;
139struct SAM
140{
141 struct state
142 {
143 int len, link, nxt[MAXALP];
144 int leftmost; //某个状态的right集合中r值最小的
145 int rightmost;//某个状态的right集合的r的最大值
146 int Right; //right集合大小
147 };
148 state st[N*2];
149 char S[N];
150 int sz, last,rt;
151 char s[N];
152 int cnt[2*N],rk[2*N];//for radix sort
153 void init()
154 {
155 sz = 0;
156 last = rt = ++sz;
157 st[1].len = 0;
158 st[1].link=-1;
159 st[1].rightmost=0;
160 ms(st[1].nxt,-1);
161 }
162 void extend(int c,int head)
163 {
164 int cur = ++sz;
165 st[cur].len = st[last].len + 1;
166 st[cur].leftmost = st[cur].rightmost = head;
167 memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
168 int p;
169 for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
170 st[p].nxt[c] = cur;
171 if (p == -1) {
172 st[cur].link = rt;
173 } else {
174 int q = st[p].nxt[c];
175 if (st[p].len + 1 == st[q].len) {
176
177 st[cur].link = q;
178 } else {
179 int clone = ++sz ;
180 st[clone].len = st[p].len + 1;
181 st[clone].link = st[q].link;
182 memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
183 st[clone].leftmost = st[q].leftmost;
184 st[clone].rightmost = st[q].rightmost;
185 for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
186 st[p].nxt[c] = clone;
187 st[q].link = st[cur].link = clone;
188 }
189 }
190 last = cur;
191 }
192 void topo()
193 {
194 ms(cnt,0);
195 for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
196 for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
197 for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
198 }
199 void pre() //跑拓扑序，预处理一些东西
200 {
201 for ( int i = sz ; i >= 2 ; i--)
202 {
203 int v = rk[i];
204 int fa = st[v].link;
205 if (fa==-1) continue;
206 st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
207 st[fa].Right += st[v].Right;
208 }
209 }
210 void solve()
211 {
212
213 LL ans = 0 ;
214 for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
215 ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
216 printf("%lld\n",ans);
217 }
218 int LCS(char *s)
219 {
220 int ans = 0,len = 0 ;
221 int p = rt;
222 for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
223 {
224 int ID = s[i]-'a';
225 if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
226 else
227 {
228 while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
229 if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
230 }
231 // printf("len:%d\n",len);
232 ans = max(ans,len);
233 }
234 return ans;
235 }
236}A;
237char B[N];
238int main()
239{
240#ifndef ONLINE_JUDGE
241 freopen("./in.txt","r",stdin);
242#endif
243 A.init();
244 cin>>A.S>>B;
245 for ( int i = 0 ,len=strlen(A.S) ; i < len ; i++) A.extend(A.S[i]-'a',i);
246 int ans = A.LCS(B);
247 cout<<ans<<endl;
248#ifndef ONLINE_JUDGE
249 fclose(stdin);
250#endif
251 return 0;
252}