SPOJ bsubstr

题目大意：给你一个长度为n的字符串，求出所有不同长度的字符串出现的最大次数。

n<=250000

如：abaaa

输出：

spoj上的时限卡的太严，必须使用O(N)的算法那才能过掉，所以采用后缀自动机解决。

一个字符串出现的次数，即为后缀自动机中该字符串对应的节点的right集合的大小，right集合的大小等于子树中叶子节点的数目。

令dp[i]表示长度为i的字符串出现的最大次数。dp[i]可以通过在后缀链接树中从叶子节点到根节点依次求出。

最后，按长度从大到小，用dp[i]去更新dp[i-1]。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

#define MAXN 250005

#define MAXC 26

struct node

{

    int go[MAXC],sufflink,step,right;

    void clear()

    {memset(go,,sizeof go);

        sufflink=step=right=;

    }

}tree[MAXN<<];

int dp[MAXN],cnt[MAXN],rk[MAXN<<],root,tot,cur,last,len,ans;

char s[MAXN];

void insert(int val)

{

    int p,q;

    tree[last].go[val]=++tot;

    cur=tot;

    tree[cur].clear();

    tree[cur].step=tree[last].step+;

    tree[cur].right++;

    for(p=tree[last].sufflink;p&&tree[p].go[val]==;p=tree[p].sufflink)

        tree[p].go[val]=cur;

    if(p==)

    tree[cur].sufflink=root;

    else

    {

        q=tree[p].go[val];

        if(tree[p].step+==tree[q].step)

        tree[cur].sufflink=q;

        else

        {

            tree[++tot].clear();

            tree[tot]=tree[q];

            tree[tot].right=;

            tree[tot].step=tree[p].step+;

            tree[cur].sufflink=tree[q].sufflink=tot;

            for(;tree[p].go[val]==q;p=tree[p].sufflink)

                tree[p].go[val]=tot;

            }

    }

    last=cur;

}

void calc()

{

    int temp;

    for(int i=;i<=tot;i++)cnt[tree[i].step]++;

    for(int i=;i<=len;i++)cnt[i]+=cnt[i-];

    for(int i=;i<=tot;i++)rk[cnt[tree[i].step]--]=i;

    for(int i=tot;i>;i--)

    {

        temp=tree[rk[i]].sufflink;

        if(tree[rk[i]].right>dp[tree[rk[i]].step])dp[tree[rk[i]].step]=tree[rk[i]].right;

        if(temp)tree[temp].right+=tree[rk[i]].right;

    }

    for(int i=len-;i>=;i--)

        if(dp[i+]>dp[i])dp[i]=dp[i+];

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

    printf("%d\n",dp[i]);

}

int main()

{

    while(~scanf("%s",s))

    {

    root=last=cur=tot=;

        tree[].clear();

    memset(dp,,sizeof dp);

    memset(cnt,,sizeof cnt);

     len=strlen(s);

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

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

    calc();

}

    return ;

巴特西

SPOJ bsubstr

最新文章

热门文章