学步园

Longest Common Substring

坑死了   p什么的np什么的q什么的nq什么的 -  -

都注意了构造还是写错了TAT

利用后缀自动机的性质:能接受所有子串

也就是说能接受的就一定是该串的子串

失配时要沿父亲走  原理同AC自动机

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NODE = 250010<<1,CH = 26,root=1;
int ch[NODE][CH],val[NODE],par[NODE],sz,last;

inline char idx(char c) {return c-'a';}

inline int NN(int v=0)
{
    memset(ch[sz],0,sizeof(ch[sz]));
    val[sz]=0;
    par[sz]=0;
    return sz++;
}

inline void init()
{
    sz=0;
    NN();
    NN();
    last=root;
}

inline void append(int c)
{
    int p=last,np=NN(val[p]+1);
    while(p&&!ch[p][c])
        ch[p][c]=np,p=par[p];
    if(!p)
        par[np]=root;
    else
    {
        int q=ch[p][c];
        if(val[p]+1==val[q])
            par[np]=q;
        else
        {
            int nq=sz++;    ///NN
            val[nq]=val[p]+1;
            memcpy(ch[nq],ch[q],sizeof(ch[nq]));
            par[nq]=par[q];
            par[np]=par[q]=nq;
            while(p&&ch[p][c]==q)
                ch[p][c]=nq,p=par[p];
        }
    }
    last=np;
}

int find(char *s)
{
    int u=root,ans=0,cnt=0,f=0;
    for(;*s;s++,ans=max(cnt,ans))
    {
        int c= idx(*s);
        while(!ch[u][c])
        {
            u=par[u];
            cnt=val[u];
            if(!u)
            {
                u=root;
                cnt=0;
                f=1;
                break;
            }
        }
        //puts("");
        if(f)
            f=0;
        else
        {
            cnt++;
            u=ch[u][c];
        }
    }
    return max(ans,cnt);
}

void solve(char *s)
{
        init();
        for(int i=0;*s;s++)
            append(idx(*s));
        scanf("%s",s);
        printf("%d",find(s));
}

char s[NODE];
int main()
{
    //freopen("b.in","r",stdin);
    scanf("%s",s);
    solve(s);
    return 0;
}
/*
abcdeeefg
eeaef
*/