最长公共子串 Longest Common Substring SPOJ LCS

模板题，数组要开的大一点

#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;
    void init()
    {
        last = tot=0;
        memset(nxt,-1,sizeof(nxt));
        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;
    }
    int fid(char *s)
    {
        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;
            }
            res = max(res,tmp);
        }
        return res;
    }
}SAM;
char s[maxn],t[maxn];
int main()
{
    while(~scanf("%s",s))
    {
        SAM.init();
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
            SAM.add(s[i]-'a');
        }
        scanf("%s",t);
        printf("%d\n",SAM.fid(t));
    }
    return 0;
}