SPOJ NSUBSTR Substrings【后缀自动机】

例题

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long
using namespace std;
const int N=2010000;
char s[N];
int fa[N],ch[N][26],len[N],siz[N];
int lst=1,node=1,l,t[N],A[N];
ll ans;
void Extend(int c)
{
    int f=lst,p=++node;lst=p;
    len[p]=len[f]+1;siz[p]=1;

    while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
    if(!f) {fa[p]=1;return;}
    int x=ch[f][c],y=++node;
    if(len[f]+1==len[x]) {fa[p]=x;node--;return;}
    len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;
    memcpy(ch[y],ch[x],sizeof(ch[y]));
    while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
}
int F[N];
int main()
{
    scanf("%s",&s[1]);
    int l = strlen(&s[1]);
    for(int i=1;i<=l;i++) Extend(s[i]-'a');
    for(int i=1;i<=node;i++) t[len[i]]++;
    for(int i=1;i<=node;i++) t[i]+=t[i-1];
    for(int i=1;i<=node;i++) A[t[len[i]]--]=i;
    for(int i=node;i>=1;i--)
    {
        int now=A[i];siz[fa[now]]+=siz[now];
        F[len[now]]=max(siz[now],F[len[now]]);
    }
    for(int i=l;i>=1;i--)
    {
        F[i]=max(F[i],F[i+1]);
    }
    for(int i=1;i<=l;i++)
    {
        printf("%d\n",F[i]);
    }
    return 0;
}