C++(g++ 7.5.0) 解法, 执行用时: 175ms, 内存消耗: 88812K, 提交时间: 2023-04-15 16:43:29

#include<bits/stdc++.h>

using namespace std;

const int N = 2.5e5 + 10, M = N << 1;
int ch[M][26], len[M], fa[M], np = 1, tot = 1;
long long cnt[M], f[N];
vector<int> g[M];
char s[N];

void extend(int c)
{
	int p = np; np = ++tot;
	len[np] = len[p] + 1, cnt[np] = 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np;
		p = fa[p];
	}
	if (!p) {
		fa[np] = 1;
	}
	else {
		int q = ch[p][c];
		if (len[q] == len[p] + 1) {
			fa[np] = q;
		}
		else {
			int nq = ++tot;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q], fa[q] = fa[np] = nq;
			while (p && ch[p][c] == q) {
				ch[p][c] = nq;
				p = fa[p];
			}
			memcpy(ch[nq], ch[q], sizeof ch[q]);
		}
	}
}

void dfs(int u)
{
	for (auto son : g[u]) {
		dfs(son);
		cnt[u] += cnt[son];
	}
	int l = len[fa[u]] + 1, r = len[u];
	f[r] = max(1ll * f[r], 1ll * cnt[u]);
}

signed main()
{
	scanf("%s", s);
	int n = strlen(s);
	for (int i = 0; s[i]; ++i) {
		extend(s[i] - 'a');
	}
	for (int i = 2; i <= tot; ++i) {
		g[fa[i]].emplace_back(i);
	}
	dfs(1);
	for (int i = n - 1; i >= 1; --i) {
		f[i] = max(f[i], f[i + 1]);
	}
	for (int i = 1; i <= n; ++i) {
		printf("%lld\n", f[i]);
	}

	return 0;
}

C++ 解法, 执行用时: 85ms, 内存消耗: 61336K, 提交时间: 2022-07-27 13:04:33

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
char s[N];
int id[N],cnt[N],r[N];
int last,tot;
int trie[N<<1][26],fail[N<<1],len[N<<1];
void extend(int ch)
{
	int p=last,np=++tot;
	last=np;
	len[np]=len[p]+1;
	while(p&&!trie[p][ch]){trie[p][ch]=np;p=fail[p];}
	if(!p)fail[np]=1;
	else
	{
		int q=trie[p][ch];
		if(len[p]+1==len[q])fail[np]=q;
		else
		{
			int nq=++tot;
			len[nq]=len[p]+1;
			memcpy(trie[nq],trie[q],sizeof(trie[q]));
			fail[nq]=fail[q];
			fail[q]=fail[np]=nq;
			while(trie[p][ch]==q){trie[p][ch]=nq;p=fail[p];}
		}
	}
	r[np]=1;
}
void build(char *w)
{
	int l=(int)strlen(w+1);
	for(int i=1;i<=tot;i++)cnt[len[i]]++;
	for(int i=1;i<=l;i++)cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;i++)id[cnt[len[i]]--]=i;
	for(int i=tot;i;i--){r[fail[id[i]]]+=r[id[i]];}
}
int F[N];
int main()
{
	scanf("%s",s+1);
	int Len=(int)strlen(s+1);
	last=tot=1;
	for(int i=1;i<=Len;i++)extend(s[i]-'a');
	build(s);
	for(int i=1;i<=tot;i++)F[len[i]]=max(F[len[i]],r[i]);
	for(int i=1;i<=Len;i++)printf("%d\n",F[i]);
	return 0;
}