后缀自动机三·重复旋律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 ;
}