Longest Common Substring II [后缀自动机]

注意更新祖先的状态

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define cl(a) memset(a,0,sizeof(a))
#define ll long long
#define pb(i) push_back(i)
#define mp make_pair
using namespace std;
const int maxn=2e6;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
typedef pair<int,int> PII;
ll fpow(ll n, ll k, ll p = mod)
{
    ll r = 1;
    for (; k; k >>= 1)
    {
        if (k & 1) r = r * n%p;
        n = n * n%p;
    }
    return r;
}
ll inv(ll a, ll p = mod)
{
    return fpow(a, p - 2, p);
}
//head

struct Trie
{
    int nxt[maxn][26],f[maxn],l[maxn],last,tot;
    int cnt[maxn];
    int t[maxn],A[maxn],mmin[maxn];
    void init()
    {
        last = tot=0;
        memset(nxt,-1,sizeof(nxt));
        memset(mmin,inf,sizeof(mmin));
        f[0]=-1;
        l[0]=0;
    }
    void add(int x)
    {
        int p=last;
        int np=++tot;
        l[np]=l[p]+1;
        memset(nxt[np],-1,sizeof(nxt[np]));
        while(~p&&nxt[p][x]==-1) nxt[p][x]=np,p=f[p];
        if(p==-1) f[np]=0;
        else
        {
            int q= nxt[p][x];
            if(l[q]!=l[p]+1)
            {
                int nq=++tot;
                l[nq]=l[p]+1;
                memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
                f[nq]=f[q];
                f[q]=f[np]=nq;
                while(~p&&nxt[p][x]==q) nxt[p][x]=nq,p=f[p];
            }
            else f[np]=q;
        }
        last=np;
    }
    void solve()
    {
        for(int i=1; i<=tot; i++) t[l[i]]++;
        for(int i=1; i<=tot; i++) t[i]+=t[i-1];
        for(int i=1; i<=tot; i++) A[t[l[i]]--]=i;
    }
    int fid(char *s)
    {
        memset(cnt,0,sizeof(cnt));
        int len = strlen(s);
        int res=0,tmp=0,u=0;
        for(int i=0; i<len; i++)
        {
            int x= s[i]-'a';
            if(nxt[u][x]!=-1)tmp++,u=nxt[u][x];
            else
            {
                while(~u&&nxt[u][x]==-1) u=f[u];
                if(~u) tmp = l[u]+1,u=nxt[u][x];
                else tmp=0,u=0;
            }
            cnt[u]=max(cnt[u],tmp);
        }
        for(int i=tot; i>=1; i--)
        {
            int now = A[i];
            cnt[f[now]]=max(cnt[f[now]],cnt[now]);
            cnt[f[now]]=min(cnt[f[now]],l[f[now]]);
            mmin[now] = min(mmin[now],cnt[now]);
        }
        for(int i=1; i<=tot; i++)
        {
            res=max(res,mmin[i]);
        }
        return res;
    }
} SAM;
char s[maxn],t[maxn];
int main()
{
    scanf("%s",s);
    SAM.init();
    int len=strlen(s);
    for(int i=0; i<len; i++)
    {
        SAM.add(s[i]-'a');
    }
    SAM.solve();
    int ans=0;
    while(~scanf("%s",t))
    {
    ans =inf;
    ans = SAM.fid(t);
    }
    printf("%d\n",ans);
    return 0;
}