SPOJ 8222 NSUBSTR - Substrings

http://www.spoj.com/problems/NSUBSTR/

题意：

F(x)定义为字符串S中所有长度为x的子串重复出现的最大次数

输出F[1]~F[len(S)]

用字符串S构建后缀自动机

若子串 str ∈状态s，那么子串str 在字符串S中出现的次数就是| Right(s) |

显然不能枚举所有状态的所有子串

但是我们可以线性的时间得到F[Max(s)]= | Right(s) |

然后再对F做一个后缀最大值即可

如何得到一个状态Right集合的大小？

一个状态s的Right集合就是Parent树上，s的子树中叶子节点Right集合的并集

所以可以从parent树上底层向上层更新，即将底层节点的Right并入父节点的Right

这个可以通过拓扑排序实现

#include<cstdio>

#include<cstring>

#define N 250002

#define max(x,y) ((x)>(y) ? (x) : (y))

char s[N];

int tot=,fa[N<<],len[N<<],ch[N<<][];

int last=,p,np,q,nq;

int front[N<<],nxt[N<<],to[N<<],cnt;

int r[N<<],f[N];

int v[N<<],sa[N<<];

void extend(int c)

{

    len[np=++tot]=len[last]+;

    for(p=last;p && !ch[p][c]; p=fa[p]) ch[p][c]=np;

    if(!p) fa[np]=;

    else

    {

        q=ch[p][c];

        if(len[q]==len[p]+) fa[np]=q;

        else

        {

            len[nq=++tot]=len[p]+;

            memcpy(ch[nq],ch[q],sizeof(ch[nq]));

            fa[nq]=fa[q];

            fa[q]=fa[np]=nq;

            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;

        }

    }

    last=np;

}

int main()

{

    scanf("%s",s+);

    int n=strlen(s+);

    for(int i=;i<=n;++i)

    {

        r[tot+]=;

        extend(s[i]-'a');

    }

    for(int i=;i<=tot;++i) v[len[i]]++;

    for(int i=;i<=n;++i) v[i]+=v[i-];

    for(int i=;i<=tot;++i) sa[v[len[i]]--]=i;

    for(int i=tot;i;--i) r[fa[sa[i]]]+=r[sa[i]];

    for(int i=;i<=tot;++i) f[len[i]]=max(f[len[i]],r[i]);

    for(int i=n-;i;--i) f[i]=max(f[i],f[i+]);

    for(int i=;i<=n;++i) printf("%d\n",f[i]);

}

巴特西

SPOJ 8222 NSUBSTR - Substrings

最新文章

热门文章