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).

Example

Input:

ababa

Output:

3
2
2
1
1

题解

肯定先建个SAM

对于每个串维护一个siz，表示这个串出现的次数，然后统计一下就好啦

#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]);
}