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
************************************************ */
#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lnxt l,m,rt<<1
#define rnxt m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=3E5;
struct SAM
{
struct node
{
node *nxt[26],*fa;int len;
node(int M) {len=M;fa=0;memset(nxt,0,sizeof(nxt));}
};
typedef node* P_node;
P_node ro,lst;
SAM() {ro=new node(0);lst=ro;}
void Insert(char ch)
{
int ID=ch-'a';P_node p=lst,np=new node(lst->len+1);
while (p&&!p->nxt[ID]) p->nxt[ID]=np,p=p->fa;
if (!p) np->fa=ro; else
{
P_node q=p->nxt[ID];
if (p->len+1==q->len) np->fa=q; else
{
P_node nq=new node(p->len+1);
memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
nq->fa=q->fa;q->fa=nq;np->fa=nq;
while (p&&p->nxt[ID]==q) p->nxt[ID]=nq,p=p->fa;
}
}
lst=np;
}
void make_SAM(char *s) {for (int i=0; s[i]!='\0';i++) Insert(s[i]);}
int LCS(char *s) //求此后缀自动机对应字符串与s的LCS
{
int ans=0,len=0;P_node p=ro;
for (int i=0;s[i]!='\0';i++)
{
int ID=s[i]-'a';
if (p->nxt[ID]) p=p->nxt[ID],len++; else
{
while (p&&!p->nxt[ID]) p=p->fa;
if (!p) p=ro,len=0; else len=p->len+1,p=p->nxt[ID];
}
ans=max(ans,len); //从所有len中刷出最优解
}
return ans;
}
};
SAM sam;
char A[N],B[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
scanf("%s %s",A,B);
// cout<<A<<endl;
// cout<<B<<endl;
sam.make_SAM(A);
int ans = sam.LCS(B);
printf("%d\n",ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
不过还是比较喜欢写静态的？
参考了zqc大爷的代码风格：
/* ***********************************************
Author :111qqz
Created Time :2017年11月03日 星期五 18时20分42秒
File Name :2774_SAM.cpp
************************************************ */
#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lnxt l,m,rt<<1
#define rnxt m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int maxn = 5E5;
struct node{
node*nxt[26],*fail;
LL len,cnt;
int ind;
int occ;
};
struct SAM{
node no[maxn];
node*root;
int cnt;
node*newnode(){
return &no[cnt++];
}
SAM(){
cnt = 0;
root = newnode();
}
node*add(int c,node*p){
node*cur = newnode();
cur->len = p->len+1;
while(p&&!p->nxt[c]){
p->nxt[c] = cur;
p = p->fail;
}
if(!p){
cur->fail = root;
return cur;
}
node*q = p->nxt[c];
if(p->len+1==q->len){
cur->fail = q;
}else{
node*nq = newnode();
*nq = *q;
q->fail = cur->fail = nq;
nq->len = p->len+1;
while(p&&p->nxt[c]==q){
p->nxt[c] = nq;
p = p->fail;
}
}
return cur;
}
int LCS(string s)
{
// cout<<"S:"<<s<<endl;
int ans=0,len=0;
node *p=root;
for ( auto i:s)
{
int ID = i-'a';
//cout<<"id:"<<ID<<" s[i]:"<<i<<" i:"<<i<<endl;
if (p->nxt[ID]) p=p->nxt[ID],len++;
else
{
while (p&&!p->nxt[ID]) p=p->fail;
if (!p) p=root,len=0;else len=p->len+1,p=p->nxt[ID];
}
ans = max(ans,len);
}
return ans;
}
};
SAM sam;
string A,B;
int main()
{
#ifndef ONLINE_JUDGE
// freopen("./in.txt","r",stdin);
#endif
node *cur =sam.root;
cin>>A>>B;
for ( auto i:A) cur = sam.add(i-'a',cur);
int ans = sam.LCS(B);
printf("%d\n",ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
/* ***********************************************
Author :111qqz
Created Time :2017年11月15日 星期三 19时06分15秒
File Name :SAM.cpp
************************************************ */
#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
#define MAXALP 30
const int N=5E5+7;
struct SAM
{
struct state
{
int len, link, nxt[MAXALP];
int leftmost; //某个状态的right集合中r值最小的
int rightmost;//某个状态的right集合的r的最大值
int Right; //right集合大小
};
state st[N*2];
char S[N];
int sz, last,rt;
char s[N];
int cnt[2*N],rk[2*N];//for radix sort
void init()
{
sz = 0;
last = rt = ++sz;
st[1].len = 0;
st[1].link=-1;
st[1].rightmost=0;
ms(st[1].nxt,-1);
}
void extend(int c,int head)
{
int cur = ++sz;
st[cur].len = st[last].len + 1;
st[cur].leftmost = st[cur].rightmost = head;
memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
int p;
for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
st[p].nxt[c] = cur;
if (p == -1) {
st[cur].link = rt;
} else {
int q = st[p].nxt[c];
if (st[p].len + 1 == st[q].len) {
st[cur].link = q;
} else {
int clone = ++sz ;
st[clone].len = st[p].len + 1;
st[clone].link = st[q].link;
memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
st[clone].leftmost = st[q].leftmost;
st[clone].rightmost = st[q].rightmost;
for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
st[p].nxt[c] = clone;
st[q].link = st[cur].link = clone;
}
}
last = cur;
}
void topo()
{
ms(cnt,0);
for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
for (int i = 1 ; i <= sz ;i++) rk[cnt[st[i].len]--] = i;
}
void pre() //跑拓扑序，预处理一些东西
{
for ( int i = sz ; i >= 2 ; i--)
{
int v = rk[i];
int fa = st[v].link;
if (fa==-1) continue;
st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
st[fa].Right += st[v].Right;
}
}
void solve()
{
LL ans = 0 ;
for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
printf("%lld\n",ans);
}
int LCS(char *s)
{
int ans = 0,len = 0 ;
int p = rt;
for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
{
int ID = s[i]-'a';
if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
else
{
while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
}
// printf("len:%d\n",len);
ans = max(ans,len);
}
return ans;
}
}A;
char B[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
A.init();
cin>>A.S>>B;
for ( int i = 0 ,len=strlen(A.S) ; i < len ; i++) A.extend(A.S[i]-'a',i);
int ans = A.LCS(B);
cout<<ans<<endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}