建后缀自动机

然后统计次数，只需要算出right集合的大小即可，

然后更新f[l[i]]和rit[i]取个max

然后根据rit集合短的一定包含长的的性质，从后往前更新一遍即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define maxn 500005struct sam{	char s[maxn];	int len;	int last,cnt,f[maxn];	int h[maxn],to[maxn],ne[maxn],en,rit[maxn];	int go[maxn][26],l[maxn],fa[maxn];	void init()	{		last=cnt=1;		memset(go,0,sizeof go);		memset(h,-1,sizeof h);		en=0;	}	void addedge(int a,int b)	{to[en]=b;ne[en]=h[a];h[a]=en++;}	void add(int x)	{//		printf("add %d\n",x);		int p=last,np=last=++cnt;l[np]=l[p]+1;rit[np]=1;		for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;		if (!p) fa[np]=1;		else		{			int q=go[p][x];			if (l[q]==l[p]+1) fa[np]=q;			else			{				int nq=++cnt;l[nq]=l[p]+1;				memcpy(go[nq],go[q],sizeof go[q]);				fa[nq]=fa[q];				fa[q]=fa[np]=nq;				for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;			}		}	}	void dfs(int o)	{		for (int i=h[o];i>=0;i=ne[i])		{			dfs(to[i]);			rit[o]+=rit[to[i]];		}		f[l[o]]=max(f[l[o]],rit[o]);	}	void solve()	{		scanf("%s",s+1);//		printf("%s\n",s+1);		len=strlen(s+1);//		printf("len is %d\n",len);		F(i,1,len) add(s[i]-'a');		F(i,1,cnt) addedge(fa[i],i);		dfs(1);		D(i,len,1) f[i]=max(f[i+1],f[i]);		F(i,1,len) printf("%d\n",f[i]);	}}SAM;int main(){	SAM.init();	SAM.solve();}