题目描述

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

输入输出格式

输入格式：

 

String S consists of at most 250000 lowercase latin letters.

 

输出格式：

 

Output |S| lines. On the i-th line output F(i).

 

输入输出样例

输入样例#1： 

ababa

输出样例#1： 

32211 对于每个节点x，i<=max{x}的f(i)都可以被size[x]更新，所以差分打个标记就可以了hhhh 今天刷后缀自动机真过瘾hhhh

#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 1000005using namespace std;int f[maxn],ch[maxn][26];int l[maxn],siz[maxn],n;int tag[maxn],cnt=1,pre=1;int a[maxn],c[maxn];char s[maxn];inline void ins(int x){	int p=pre,np=++cnt; 	pre=np,l[np]=l[p]+1;	siz[np]=1;		for(;p&&!ch[p][x];p=f[p]) ch[p][x]=np;	if(!p) f[np]=1;	else{		int q=ch[p][x];		if(l[q]==l[p]+1) f[np]=q;		else{			int nq=++cnt;			l[nq]=l[p]+1;			memcpy(ch[nq],ch[q],sizeof(ch[q]));			f[nq]=f[q];			f[q]=f[np]=nq;			for(;ch[p][x]==q;p=f[p]) ch[p][x]=nq;		}	}}inline void build(){	for(int i=0;i
            
             =0;i--) c[i]+=c[i+1]; for(int i=1;i<=cnt;i++) a[c[l[i]]--]=i;}inline void solve(){ for(int i=1;i<=cnt;i++){ int now=a[i]; siz[f[now]]+=siz[now]; tag[l[now]]=max(tag[l[now]],siz[now]); } for(int i=n;i;i--) tag[i]=max(tag[i],tag[i+1]);}int main(){ scanf("%s",s); n=strlen(s); build(); solve(); for(int i=1;i<=n;i++) printf("%d\n",tag[i]); return 0;}