# spoj 8222 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).

ababa

3
2
2
1
1

### 题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 250010
using namespace std;
int dis[N<<1],fa[N<<1],ch[N<<1][26],siz[N<<1],last=1,sz=1,root=1,len;
char s[N];
void insert(int x)
{
int now=++sz,pre=last;last=now;
dis[now]=dis[pre]+1,siz[now]=1;
for (;pre && !ch[pre][x];pre=fa[pre]) ch[pre][x]=now;
if (!pre) fa[now]=root;
else
{
int q=ch[pre][x];
if (dis[q]==dis[pre]+1)
fa[now]=q;
else
{
int nows=++sz;dis[nows]=dis[pre]+1;
memcpy(ch[nows],ch[q],sizeof ch[q]);
fa[nows]=fa[q],fa[now]=fa[q]=nows;
for (;pre && ch[pre][x]==q;pre=fa[pre]) ch[pre][x]=nows;
}
}
}
int ton[N<<1],ti[N<<1],f[N<<1];
void work()
{
for (int i=1;i<=sz;i++) ton[dis[i]]++;
for (int i=1;i<=len;i++) ton[i]+=ton[i-1];
for (int i=1;i<=sz;i++) ti[ton[dis[i]]--]=i;
for (int i=sz;i;i--)
siz[fa[ti[i]]]+=siz[ti[i]];
for (int i=sz;i;i--)
f[dis[ti[i]]]=max(f[dis[ti[i]]],siz[ti[i]]);
}
main()
{
scanf("%s",s+1),len=strlen(s+1);
for (int i=1;i<=len;i++) insert(s[i]-'a');
work();
for (int i=1;i<=len;i++) printf("%d\n",f[i]);
}