SPOJ NSUBSTR(后缀自动机)-白红宇

SPOJ NSUBSTR(后缀自动机)

阅读量：7216 次

发布时间：2019-06-29

本文共 1616 字，大约阅读时间需要 5 分钟。

题目链接：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
      
       #include
       
        #include
        
         #include
         
          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
          
           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\n",dp[i]);    return 0;}