我们还从一个非常经典的题目出发，最长公共子串问题。给定两个字符串S和T，求S和T的最长公共子串的长度。比如abcdefg和abacabca的最长公共子串是abc
这是一道经典的动态规划问题，大致思路就是用fi表示同时以S[i]和T[j]结尾的最长公共子串的长度。下面看伪代码：
Ans = 0
For i = 1...S.len
For j = 1...T.len
If S[i] == T[i]
F[i][j] = F[i - 1][j - 1] + 1
If F[i][j] > Ans
Ans = F[i][j]
Print AnsDP的时间复杂度是O(S.len * T.len)，但其实这道题利用后缀自动机，时间复杂度只到O(S.len + T.len)，下图就是字符串”aabbabd”的后缀自动机：
后缀自动机就是能接受并且只接受S的后缀字符串。也就是说，你可以发现对于S的后缀，我们都可以从S出发沿着字符标示的路径（蓝色实线）转移，最终到达终结状态，也就是红色的节点
例如"bd"对应的路径是S59，"abd"对应的路径是S189，"abbabd"对应的路径是S184679。而对于不是S后缀的字符串，你会发现从S出发，最后会到达非终结状态或者“无路可走”。特别的，对于S的子串，最终会到达一个合法状态。例如"abba"路径是S1846，"bbab"路径是S5467。而对于其他不是S子串的字符串，最终会“无路可走”。 例如"aba"对应S18X，"aaba"对应S123X。（X表示没有转移匹配该字符）
首先我们先介绍一个概念：子串的结束位置集合endpos。对于S的一个子串t，endpos(t) = t在S中所有出现的结束位置集合。还是以S="aabbabd"为例，endpos("ab") = {3, 6}，因为"ab"一共出现了2次，结束位置分别是3和6。同理endpos("a") = {1, 2, 5}, endpos("abba") = {5}
我们把S的所有子串的endpos都求出来。如果两个子串的endpos相等，就把这两个子串归为一类。最终这些endpos的等价类就构成的SAM的状态集合。例如对于S="aabbabd"：
其中maxlen是一个状态包含的子串中，最长子串的长度。有了后缀自动机和每个状态的maxlen，我们就能求解S和T的最长公共子串了。具体做法是先求出S的后缀自动机，然后用T的每一个字符在S的后缀自动机上跑一遍。这里跑一遍的意思就是从初始状态开始，根据每一个字符T[i]在自动机的不同状态之间转移
举个例子，假设S=aabbabd，S的后缀自动机就是一开始的那张图
T=abbbaabbab。我们要找S和T的最长公共子串，就从状态S开始匹配，用u表示当前的状态，l表示当前匹配的长度。基本思路就是如果当前状态u没有标识T[i]的蓝色实线转移，我们就沿着绿色虚线向上找，不断令u等于u的绿色虚线指向的状态，同时令l = u.maxlen，直到u存在标识T[i]的转移或者u走到头了
如果最后u走到头了，我们就令u=S，l=0，从T[i+1]开始重新匹配。否则，我们就沿着蓝色实线转移，令u等于u的蓝色实线指向的状态，同时令l=l+1。然后再从T[i+1]继续匹配
具体来说，字符串T的完整匹配过程如下：
一开始u=S，l=0，我们要匹配T[1]=a，刚好u有标识a的边，所以我们直接移动到u=1, l=1
现在u=1, l=1，我们要匹配T[2]=b，刚好u有标识b的边，所以我们直接移动到u=8, l=2
现在u=8, l=2, 我们要匹配T[3]=b，刚好u有标识b的边，所以我们直接移动到u=4, l=3
现在u=4, l=3, 我们要匹配T[4]=b，u没有标识b的边，所以沿绿色退到u=5, l=maxlen[5]=1
现在u=5, l=1, 我们要匹配T[4]=b，u有标识a的边，所以我们移动到u=4, l=2
现在u=4, l=2, 我们要匹配T[5]=a，u有标识a的边，所以我们移动到u=6, l=3
现在u=6, l=3, 我们要匹配T[6]=a，u没有标识a的边，所以沿绿色退到u=1, l=maxlen[1]=1
现在u=1, l=1, 我们要匹配T[6]=a，u有标识a的边，所以我们移动到u=2, l=2
现在u=2, l=2, 我们要匹配T[7]=b，u有标识b的边，所以我们移动到u=3, l=3
现在u=3, l=3, 我们要匹配T[8]=b，u有标识b的边，所以我们移动到u=4, l=4
现在u=4, l=4, 我们要匹配T[9]=a，u有标识a的边，所以我们移动到u=6, l=5
现在u=6, l=5, 我们要匹配T[10]=b，u有标识b的边，所以我们移动到u=7, l=6
这样T就匹配完了，在匹配过程中，l的最大值就是最长公共子串的长度，也就是6。实际上匹配T[10]的时候l等于6，也意味着最长公共子串是T[5]~T[10]即：aabbab；同时u=7也意味着最长公共子串是状态7中长度为6的子串，从之前的表格中我们知道也是aabbab
对于字符串S，构建S的后缀自动机的复杂度是O(S.len)的；之后对T的每个字母跑一遍匹配，复杂度是O(T.len)。所以总的复杂度是O(S.len+T.len)。最后我们给出用后缀自动机求最长公共子串的代码：
#include<iostream>
#include<string>
using namespace std;
const int MAXL = 1000000;
string s, t;
int n = 0, len, st;
int maxlen[2 * MAXL + 10], minlen[2 * MAXL + 10], trans[2 * MAXL + 10][26], slink[2 * MAXL + 10];
int new_state(int _maxlen, int _minlen, int* _trans, int _slink) {
maxlen[n] = _maxlen;
minlen[n] = _minlen;
for(int i = 0; i < 26; i++) {
if(_trans == NULL)
trans[n][i] = -1;
else
trans[n][i] = _trans[i];
}
slink[n] = _slink;
return n++;
}
int add_char(char ch, int u) {
int c = ch - 'a';
int z = new_state(maxlen[u] + 1, -1, NULL, -1);
int v = u;
while(v != -1 && trans[v][c] == -1) {
trans[v][c] = z;
v = slink[v];
// cout << v << endl;
}
// cout << z << endl;
if(v == -1) {
minlen[z] = 1;
slink[z] = 0;
return z;
}
int x = trans[v][c];
if(maxlen[v] + 1 == maxlen[x]) {
minlen[z] = maxlen[x] + 1;
slink[z] = x;
return z;
}
int y = new_state(maxlen[v] + 1, -1, trans[x], slink[x]);
slink[y] = slink[x];
minlen[x] = maxlen[y] + 1;
slink[x] = y;
minlen[z] = maxlen[y] + 1;
slink[z] = y;
int w = v;
while(w != -1 && trans[w][c] == x) {
trans[w][c] = y;
w = slink[w];
}
minlen[y] = maxlen[slink[y]] + 1;
return z;
}
int main()
{
cin >> s >> t;
len = s.size();
st = new_state(0, 0, NULL, -1);
// cout << trans[st][0] << endl;
int u = st;
for(int i = 0; i < len; i++) {
int temp = add_char(s[i], u);
u = temp;
}
u = st;
int ans = 0, cur = 0;
for(int i = 0; i < t.size(); i++) {
int c = t[i] - 'a';
while(u != -1 && trans[u][c] == -1) {
u = slink[u];
cur = maxlen[u];
}
if(u == -1) {
u = 0;
cur = 0;
continue;
}
u = trans[u][c];
cur++;
if(cur > ans) ans = cur;
}
cout << ans << endl;
return 0;
}