SPOJ NSUBSTR

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
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=250005,M=550005;
 9 char s[N];int n,last=1,cnt=1,cur=1,dis[M],ch[M][27],fa[M],size[M];
10 void build(int j){
11     int c=s[j]-'a';
12     last=cur;cur=++cnt;
13     int p=last;dis[cur]=j;
14     for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;
15     if(!p)fa[cur]=1;
16     else{
17         int q=ch[p][c];
18         if(dis[q]==dis[p]+1)fa[cur]=q;
19         else{
20             int nt=++cnt;
21             dis[nt]=dis[p]+1;
22             memcpy(ch[nt],ch[q],sizeof(ch[q]));
23             fa[nt]=fa[q];fa[q]=fa[cur]=nt;
24             for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;
25         }
26     }
27     size[cur]=1;
28 }
29 int sa[M];long long ans[N],c[N];
30 void Flr(){
31     int p;
32     for(int i=1;i<=cnt;i++)c[dis[i]]++;
33     for(int i=1;i<=n;i++)c[i]+=c[i-1];
34     for(int i=cnt;i>=1;i--)sa[c[dis[i]]--]=i;
35     for(int i=cnt;i>=1;i--){
36         p=sa[i];
37         if(size[p]>ans[dis[p]])ans[dis[p]]=size[p];
38         size[fa[p]]+=size[p];
39     }
40 }
41 void work(){
42     scanf("%s",s+1);
43     n=strlen(s+1);
44     for(int i=1;i<=n;i++)build(i);
45     Flr();
46     for(int i=1;i<=n;i++)printf("%lld
",ans[i]);
47 }
48 int main()
49 {
50     //freopen("pp.in","r",stdin);
51     work();
52     return 0;
53 }


 
原文地址:https://www.cnblogs.com/Yuzao/p/7270204.html