Description

尽管Murphyc赶在学级裁判开始前进入了未来机关的控制室，但学级裁判已经被设置为不可中断.
虽然之前利用魔法修改识别码时已经尽量减少魔力消耗，但此刻魔力仍是所剩无几。Murphyc无力地坐到了地上，眼睁睁的看着Chiaki被处以“学级裁判”.
Chiaki在弥留之际:

                           私の方こそ・・・ありがとう

                           みんなの事・・・忘れないよ・・・
                           ずっとずっと・・・忘れないよ・・・
                           この先も・・・どこかでみんなの事を応援しているからね

                           だって・・・ずっと仲间だもん

    伤心欲绝的Murphyc一个人带着Chiaki最后的话语离开了未来机关。
    尽管Murphyc从绝望残党手中逃脱，但是他发现Chiaki最后的录音被绝望所污染，为了恢复录音，Murphyc需要知道被污染的录音的最长未被污染音段，他很快解决了这个问题，回归了原来的世界.
    Murphyc的故事到此结束，但是ACMer的问题并没有解决，给你两个串(仅由小写字母组成),请问最长公共子串的长度.

Input

第一行输入长度不超过3e5的串s1
第二行输入长度不超过3e5的串s2

Output

最长公共子串(Longest Common Substring)的长度
若不存在LCS，输出0

Sample Input

watashinokatakosoarigato
minnanokotowasurenaiyo

Sample Output

3

题解：

后缀自动机(SAM)裸题，具体解释可以看如下

其实吧后缀数组(SA)利用height[]也可以解决这个问题，不过DA的SA肯定会被卡常，DC3的应该卡不到，但其实我造的数据还蛮水的hhh

不会SAM的建议先学AC自动机了解一下自动机理论还有SA，最后再去学SAM.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
inline int read()
{
    char ch=getchar();
    int i=0,f=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        i=(i<<3)+(i<<1)+ch-'0';
        ch=getchar();
    }
    return i*f;
}
struct SAM
{
    static const int KN = N << 1;
    static const int KM = 27;
    int fail[KN], net[KN][KM], len[KN], cnt, root;
    int rig[KN],sum[KN];
    int newnode(int _len)
    {
        memset(net[cnt], -1, sizeof(net[cnt]));
//        fail[cnt] = -1;
        len[cnt] = _len;
        return cnt++;
    }
    void init()
    {
        cnt = 0;
        memset(fail,-1,sizeof(fail));
        root = newnode(0);
    }
    int add(int p, int x)//u--np,v---p
    {
        int np=newnode(len[p]+1);
        rig[np]=1;
        while(~p && net[p][x] == -1)    net[p][x] = np, p = fail[p];
        if(p == -1) fail[np] = root;
        else
        {
            int q = net[p][x];
            if(len[q] == len[p] + 1)    fail[np] = q;
            else
            {
                int nq = newnode(len[p] + 1);
                memcpy(net[nq], net[q], sizeof(net[q]));
                fail[nq] = fail[q];
                fail[q] = fail[np] = nq;
                while(~p && net[p][x] == q) net[p][x] = nq, p = fail[p];
            }
        }
        return np;
    }
    void build(char* s, char ch)
    {
        int now = root;
        for(int i = 0; s[i]; ++i)   now = add(now, s[i] - ch);
    }
    int ord[KN], pri[KN];
    void topo()
    {
        int maxVal=0;
        memset(pri, 0, sizeof(pri));
        for (int i = 0; i < cnt; ++i) maxVal = max(maxVal, len[i]), ++ pri[len[i]];
        for (int i = 1; i <= maxVal; ++i) pri[i] += pri[i - 1];
        for (int i = 0; i < cnt; ++i) ord[--pri[len[i]]] = i;
    }
    void gao(int k)
    {
        topo();
    }
} sam;
char s[N];
char ss[N];
int main()
{
    freopen("stdin.txt","r",stdin);
    freopen("stdout.txt","w",stdout);
    scanf("%s",s);
    scanf("%s",ss);
    int len1,len2;
    len1=strlen(s),len2=strlen(ss);
    sam.init();
    sam.build(s,'a');
    sam.topo();
    int cnt=0,pos=0,ans=0;
    for(int i=0; i<strlen(ss); i++)
    {
        while(~pos&&sam.net[pos][ss[i]-'a']==-1) pos=sam.fail[pos];
        if(pos==-1) pos=0,cnt=0;
        else cnt=min(sam.len[pos],cnt)+1,pos=sam.net[pos][ss[i]-'a'],ans=max(ans,cnt);
    }
    printf("%d\n",ans);
}