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).
Example
Input:
ababa Output:
3
2
2
1
1 题解:
这..比上题还简单啊,根据parent树上父节点为子节点的最大子集,直接统计size即可,
英语不好看成了求和........3WA
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=,M=;
char s[N];int n,last=,cnt=,cur=,dis[M],ch[M][],fa[M],size[M];
void build(int j){
int c=s[j]-'a';
last=cur;cur=++cnt;
int p=last;dis[cur]=j;
for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
if(!p)fa[cur]=;
else{
int q=ch[p][c];
if(dis[q]==dis[p]+)fa[cur]=q;
else{
int nt=++cnt;
dis[nt]=dis[p]+;
memcpy(ch[nt],ch[q],sizeof(ch[q]));
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;
}
}
size[cur]=;
}
int sa[M];long long ans[N],c[N];
void Flr(){
int p;
for(int i=;i<=cnt;i++)c[dis[i]]++;
for(int i=;i<=n;i++)c[i]+=c[i-];
for(int i=cnt;i>=;i--)sa[c[dis[i]]--]=i;
for(int i=cnt;i>=;i--){
p=sa[i];
if(size[p]>ans[dis[p]])ans[dis[p]]=size[p];
size[fa[p]]+=size[p];
}
}
void work(){
scanf("%s",s+);
n=strlen(s+);
for(int i=;i<=n;i++)build(i);
Flr();
for(int i=;i<=n;i++)printf("%lld\n",ans[i]);
}
int main()
{
//freopen("pp.in","r",stdin);
work();
return ;
}