spoj8222 substrings [后缀自动机]

in 题目 with 0 comment

Description

NSUBSTR - Substrings

You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string 'ababa' F(3) will be 2 because there is a string 'aba' that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|.


Input

String S consists of at most 250000 lowercase latin letters.


Output

Output |S| lines. On the i-th line output F(i).


Sample Input

ababa


Sample Output

3
2
2
1
1


Solution

没什么好分析的hh,基本裸的后缀自动机,对parent树进行Tsort(),自底向上维护r[i]的大小,注意开始赋值时每个实节点(即np,而非nq)的r赋为1,其他为0


Code

#include<bits/stdc++.h>
#define maxn 500010
//#define DEBUG
using namespace std;
int n;
int sum[maxn],tmp[maxn],f[maxn];
char ch[maxn];

struct SAM
{
    int root,tot,last;
    int son[maxn][26],fa[maxn],maxl[maxn],r[maxn];
    int addnode(int n) {return maxl[++tot]=n,tot;} 
    
    void init()
    {
        root=tot=last=1;
        memset(son,0,sizeof(son));
        memset(fa,0,sizeof(fa));
        memset(maxl,0,sizeof(maxl));
        memset(r,0,sizeof(r));
    }
    
    void add(int pos)
    {
        int x=ch[pos]-'a',np=addnode(pos),p=last;
        last=np,r[np]=1;
        for( ; p&&!son[p][x] ; p=fa[p] ) son[p][x]=np;
        if(!p) fa[np]=root;
        else
        {
            int q=son[p][x];
            if(maxl[q]==maxl[p]+1) fa[np]=q;
            else
            {
                int nq=addnode(maxl[p]+1);
                memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];
                fa[np]=fa[q]=nq;
                for( ; son[p][x]==q ; p=fa[p] ) son[p][x]=nq;
            }
        }
    }
    
    void Tsort()
    {
        for(int i=1;i<=tot;++i) sum[maxl[i]]++;
        for(int i=1;i<=n;++i) sum[i]+=sum[i-1];
        for(int i=1;i<=tot;++i) tmp[sum[maxl[i]]--]=i;
    #ifdef DEBUG
        for(int i=1;i<=tot;++i) printf("   tmp[%d]=%d   maxl[tmp[%d]]=%d\n",i,tmp[i],i,maxl[tmp[i]]);
    #endif
    }
    
    void build()
    {
        init();
        scanf("%s",ch+1);
        n=strlen(ch+1);
        for(int i=1;i<=n;++i) add(i);
        Tsort();
    }
    
    void work()
    {
        build();
    #ifdef DEBUG
        for(int i=1;i<=tot;++i)
            cerr<<"r["<<i<<"]="<<r[i]<<endl;
    #endif
        for(int i=tot;i;i--) r[fa[tmp[i]]]+=r[tmp[i]];
        for(int i=1;i<=tot;++i) f[maxl[i]]=max(f[maxl[i]],r[i]);
        for(int i=1;i<=n;++i) printf("%d\n",f[i]);
    }
    
} sam ;

int main()
{
    sam.work();
    return 0;
}

/*
Input:
ababa

Output:
3
2
2
1
1
*/

扫描二维码,在手机上阅读!
Responses