SPOJ NSUBSTR(后缀自动机)

题目链接：http://www.spoj.com/problems/NSUBSTR/

题目大意：给你一个字符串s(len(s)<=250000)，求f[i](i=1...len(s))，其中f[i]表示长度为i的子串在s中出现次数的最大值（即最大次数）

题解：第一道后缀自动机题，其实很多地方不是很懂。。。（贴上CLJ论文和一篇wlw推荐的确实不错的讲稿就跑

https://wenku.baidu.com/view/90f22eec551810a6f4248606.html

http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html
代码：

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int N=250010,M=500010;
int n,cnt,lst,son[M][26],len[M],pre[M],dp[M],in[M],f[M];
char s[N];
queue<int>q;
void add(int x)
{
    int p=lst,np=++cnt;
    len[np]=len[p]+1; f[np]=1;
    for (;p&&!son[p][x];p=pre[p]) son[p][x]=np;
    if (!p) pre[np]=1;
    else
    {
        int q=son[p][x];
        if (len[q]==len[p]+1) pre[np]=q;
        else
        {
            int nq=++cnt; len[nq]=len[p]+1;
            pre[nq]=pre[q];
            pre[q]=pre[np]=nq;
            memcpy(son[nq],son[q],sizeof son[q]);
            for (;son[p][x]==q;p=pre[p]) son[p][x]=nq;
        }
    }
    lst=np;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    lst=cnt=1;
    for (int i=1;i<=n;i++) add(s[i]-'a');
    for (int i=1;i<=cnt;i++) in[pre[i]]++;
    for (int i=1;i<=cnt;i++) if (!in[i]) q.push(i);
    while (!q.empty())
    {
        int u=q.front(); q.pop();
        if (--in[pre[u]]==0) q.push(pre[u]);
        f[pre[u]]+=f[u];
    }
    for (int i=1;i<=cnt;i++) dp[len[i]]=max(dp[len[i]],f[i]);
    for (int i=n-1;i>=1;i--) dp[i]=max(dp[i],dp[i+1]);
    for (int i=1;i<=n;i++) printf("%d
",dp[i]);
    return 0;
}