【题目大意】
求两个字符串的最长公共子串。
【思路】
对第一个字符串建立后缀自动机，第二个字符串去匹配。cnt记录当前最长公共子串的长度，而ret记录答案。
p代表位置指针，初始在rt位置。
对于第二个字符串的某一位s[i]，如果当前有s[i]孩子，则cnt+1，继续往后移动；否则沿着pre指针返回。如果pre指针返回到0，则将p回到rt，cnt清空为0;否则如果中间有点拥有s[i]孩子，cnt=step[]+1。
为什么cnt=step[]+1?不要忘了后缀自动机的本质是维护后缀，沿着pre指针跑就是往长度更小的后缀移动，某位置代表的后缀的最长长度为step[]，再加上s[i]，即是step[]+1。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=+;
int n;
char str[][MAXN];
struct SAM
{
int step[MAXN*],pre[MAXN*],next[MAXN*][];
int tot,last;
inline int newNode(int cnt)
{
step[++tot]=cnt;
pre[tot]=;
for (int i=;i<;i++) next[tot][i]=;
return tot;
} inline void extend(int x)
{
int p=last;
int np=newNode(step[p]+);
while (p && !next[p][x]) next[p][x]=np,p=pre[p];
if (!p) pre[np]=;
else
{
int q=next[p][x];
if (step[q]==step[p]+) pre[np]=q;
else
{
int nq=newNode(step[p]+);
for (int i=;i<;i++) next[nq][i]=next[q][i];
pre[nq]=pre[q];
pre[q]=pre[np]=nq;
while (p&&next[p][x]==q) next[p][x]=nq,p=pre[p];
} }
last=np;
} inline void clear()
{
int tot=;
last=newNode(tot);
} inline int Query()
{
int ret=,cnt=;
int p=;
for(int i=;str[][i];i++)
{
int index=str[][i]-'a';
if(next[p][index]) p=next[p][index],cnt++;
else
{
while (p && !next[p][index]) p=pre[p];
if(!p) p=,cnt=;
else cnt=step[p]+,p=next[p][index];
/*由于沿着pre返回得到的字符串是当前字符串的后缀，所以第一个拥有index孩子的就是最长满足的后缀，长度即为step+1*/
}
ret=max(ret,cnt);
}
return ret;
}
}suf; void init()
{
scanf("%d",&n);
scanf("%s",str[]);
int len=strlen(str[]);
suf.clear();
for (int i=;i<len;i++) suf.extend(str[][i]-'a');
scanf("%s",str[]);
} int main()
{
init();
printf("%d",suf.Query());
return ;
}