hiho一下第129周 后缀自动机二·重复旋律6

后缀自动机三·重复旋律6

时间限制:15000ms

单点时限:3000ms

内存限制:512MB

描述

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对于所有的K的答案。

解题方法提示

输入

共一行，包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。

输出

共Length(S)行，每行一个整数，表示答案。

样例输入

aab

样例输出

2

1

1

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

using namespace std;

typedef long long ll;

const int inf=0x3f3f3f3f;

const int N=1e6+;

const int M=1e6+;

int tot,slink[*N],trans[*N][],minlen[*N],maxlen[*N],edpts[*N];

char str[*N];

int n;

int containPrefix[*N],ind[*N],ans[*N+];

int newstate(int _maxlen,int _minlen,int* _trans,int _slink) {

    maxlen[++tot]=_maxlen;

    minlen[tot]=_minlen;

    slink[tot]=_slink;

    if(_trans)

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

            trans[tot][i]=_trans[i];

    return tot;

}

int add_char(char ch,int u) {

    int c=ch-'a',v=u;

    int z=newstate(maxlen[u]+,-,NULL,);

    containPrefix[z]=;

    while(v&&!trans[v][c]) {

        trans[v][c]=z;

        v=slink[v];

    }

    if(!v) {

        minlen[z]=;

        slink[z]=;

        ind[]++;

        return z;

    }

    int x=trans[v][c];

    if(maxlen[v]+==maxlen[x]) {

        slink[z]=x;

        minlen[z]=maxlen[x]+;

        ind[x]++;

        return z;

    }

    int y=newstate(maxlen[v]+,-,trans[x],slink[x]);

    slink[z]=slink[x]=y;

    ind[y]+=;

    minlen[x]=minlen[z]=maxlen[y]+;

    while(v&&trans[v][c]==x) {

        trans[v][c]=y;

        v=slink[v];

    }

    minlen[y]=maxlen[slink[y]]+;

    return z;

}

void getEndPtCount() {

    queue<int> q;

    for( int i=; i <=tot; i++ )if( !ind[i] ) {

            q.push(i);

            //edpts[i] = maxlen[i]-minlen[i]; // +1; programming convenient purpose

        }

    while( !q.empty() ) {

        int u = q.front();

        q.pop();

        if( containPrefix[u] ) edpts[u]++;

        edpts[ slink[u]] += edpts[u];

        if( !--ind[slink[u]] ) q.push(slink[u]);

    }

}

int main() {

    scanf("%s",str);

    int len=strlen(str),pre=;

    tot=;

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

        pre=add_char(str[i],pre);

    }

    getEndPtCount();

    for(int i=;i<=tot;i++){

        ans[maxlen[i]] = max(ans[maxlen[i]],edpts[i]);

    }

    int mm=;

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

        mm=ans[i]=max(ans[i],mm);

    }

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

    return ;

}