SAM版题

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ch[500010][27],len[500010],cnt[500010],fa[500010],id=1,np=1;
void extend(int c){
	int p=np;np=++id;
	cnt[np]=1;len[np]=len[p]+1;
	for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
	if(!p)fa[np]=1;
	else{
		int q=ch[p][c];
		if(len[q]==len[p]+1)fa[np]=q;
		else{
			int nq=++id;
			fa[nq]=fa[q];fa[q]=nq;fa[np]=nq;
			len[nq]=len[p]+1;
			for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
		}
	}
}
vector<int> e[500010];
int ans[250010];
void dfs(int x){
	for(int y:e[x])dfs(y),cnt[x]+=cnt[y];
	ans[len[x]]=max(ans[len[x]],cnt[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	for(char i:s)extend(i-'a');
	for(int i=2;i<=id;i++)e[fa[i]].push_back(i);
	dfs(1);
	for(int i=1;i<=s.size();i++)cout<<ans[i]<<'\n';
	return 0;
}