题目大意：
给出两个长度小于等于25W的字符串，求它们的最长公共子串。
题目链接：
算法讨论：
二分+哈希， 后缀数组， 后缀自动机。
随意做。这里面只写一下我对后缀自动机做法的理解。
首先，我们假设两个串分别为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：
1 #include2 using namespace std; 3 const int L = 250000 + 5; 4 5 struct State{ 6 int len, fa; 7 int next[26]; 8 }st[L<<1]; 9 10 struct SuffixAutomaton{11 int sz, last;12 13 void Init(){14 last = 0;15 st[0].len = 0; st[0].fa = -1;16 sz ++;17 }18 void Extend(int c){19 int cur = sz ++;20 st[cur].len = st[last].len + 1;21 int p;22 23 for(p = last; p != -1 && !st[p].next[c]; p = st[p].fa)24 st[p].next[c] = cur;25 26 if(p == -1) st[cur].fa = 0;27 else{28 int q = st[p].next[c];29 if(st[q].len == st[p].len + 1) st[cur].fa = q;30 else{31 int cle = sz ++;32 st[cle].len = st[p].len + 1;33 st[cle].fa = st[q].fa;34 for(int i = 0; i < 26; ++ i) st[cle].next[i] = st[q].next[i];35 for(; p != -1 && st[p].next[c] == q; p = st[p].fa)36 st[p].next[c] = cle;37 st[q].fa = st[cur].fa = cle;38 }39 }40 last = cur;41 }42 }SAM;43 44 char str1[L], str2[L];45 46 int main(){47 scanf("%s%s", str1, str2);48 49 int len1 = strlen(str1), len2 = strlen(str2);50 int ans = 0;51 52 SAM.Init();53 for(int i = 0; i < len1; ++ i)54 SAM.Extend(str1[i] - 'a');55 56 int p = 0, len = 0;57 for(int i = 0; i < len2; ++ i){58 int x = str2[i] - 'a';59 60 if(st[p].next[x]){61 len ++;62 p = st[p].next[x];63 }64 else{65 while(p != -1 && !st[p].next[x]) p = st[p].fa;66 if(p == -1){67 len = 0; p = 0;68 }69 else{70 len = st[p].len + 1; p = st[p].next[x];71 }72 }73 ans = max(ans, len);74 }75 76 printf("%d\n", ans);77 return 0;78 }