题目大意：
给出两个长度小于等于25W的字符串，求它们的最长公共子串。
题目链接：http://www.spoj.com/problems/LCS/
算法讨论：
二分+哈希， 后缀数组， 后缀自动机。
随意做。这里面只写一下我对后缀自动机做法的理解。
首先，我们假设两个串分别为A串和B串，我们先对建立出A串的后缀自动机，然后对于B串的每一位，我们进行如下的操作：首先从第1位开始，Parent树上的位置在root，那么对于每一次操作，如果当前结点的字符可以匹配当前B串中所考虑到的字符，那么自然就len ++,然后继续沿着Parent树向下走。如果当前失配，那么根据“在Parent树上某一个结点状态的pre指针指向的是可以接收同样后缀的状态结点”这条性质，我们在parent树上向上跳。此时，根据parent树原理，其父亲的right集合元素数目变多，字符串长度变短，那么，就可以这么考虑，刚刚在s(临时设个变量表示长度)长度的时候不能完全匹配，所以我们只有减小长度才有再次匹配成功的可能，所以要凭借Parent树来完成（因为Father的Right集合元素数多，所以字符串长度就短），我们沿着Parent树向上跳，这时会出现两种情况，第一，跳到了-1.也就是null状态，这说明B[i]（假设当前正在考虑第i个子串）没有在A串中出现，所以此时把len清0，然后Parent树上位置回root，从新考虑。第二，找到了匹配位置，那么len = st[p].len + 1, p为当前在Parent树上的位置，为什么这样呢？考虑b[i]可以在p这个状态结点成功匹配，由于我们是从Parent上找到这个结点的，所以其前面的字符一定都是匹配的。举个例子，假设我们当前已经成功匹配了2个字符（不是定是B串中的前两个字符，因为是子串），现在考虑b[i],即可能成为成功匹配的第三个字符，如果在p成功匹配，那么由于在Parent树上向上跳了，因为上面提到的性质（Parent树的父亲的状态表示的子串是其儿子的最长后缀），子串长度会变短。假设变短1，所以匹配完后长度变成了2.。。。
Codes：
#include <bits/stdc++.h>
using namespace std;
const int L = + ; struct State{
int len, fa;
int next[];
}st[L<<]; struct SuffixAutomaton{
int sz, last; void Init(){
last = ;
st[].len = ; st[].fa = -;
sz ++;
}
void Extend(int c){
int cur = sz ++;
st[cur].len = st[last].len + ;
int p; for(p = last; p != - && !st[p].next[c]; p = st[p].fa)
st[p].next[c] = cur; if(p == -) st[cur].fa = ;
else{
int q = st[p].next[c];
if(st[q].len == st[p].len + ) st[cur].fa = q;
else{
int cle = sz ++;
st[cle].len = st[p].len + ;
st[cle].fa = st[q].fa;
for(int i = ; i < ; ++ i) st[cle].next[i] = st[q].next[i];
for(; p != - && st[p].next[c] == q; p = st[p].fa)
st[p].next[c] = cle;
st[q].fa = st[cur].fa = cle;
}
}
last = cur;
}
}SAM; char str1[L], str2[L]; int main(){
scanf("%s%s", str1, str2); int len1 = strlen(str1), len2 = strlen(str2);
int ans = ; SAM.Init();
for(int i = ; i < len1; ++ i)
SAM.Extend(str1[i] - 'a'); int p = , len = ;
for(int i = ; i < len2; ++ i){
int x = str2[i] - 'a'; if(st[p].next[x]){
len ++;
p = st[p].next[x];
}
else{
while(p != - && !st[p].next[x]) p = st[p].fa;
if(p == -){
len = ; p = ;
}
else{
len = st[p].len + ; p = st[p].next[x];
}
}
ans = max(ans, len);
} printf("%d\n", ans);
return ;
}
SPOJ 1811