spoj-NSUBSTR

NSUBSTR.cpp

#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 500000 + 9;
int f[N];
char s[N];
struct SAM
{
	int l[N],ch[N][26],fa[N],cnt,S,n,r[N],last;
	void add(char cc)
	{
		int c = cc - 'a';
		int p = last,np = ++cnt; last = np;
		l[np] = ++n;
		for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
		if (!p) fa[np] = S;
		else {
			int q = ch[p][c];
			if (l[p] + 1 == l[q]) fa[np] = q;
			else {
				int nq = ++cnt;
				memcpy(ch[nq],ch[q],sizeof ch[q]);
				fa[nq] = fa[q];
				fa[np] = fa[q] = nq;
				l[nq] = l[p] + 1;
				for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
			}
		}
	}
	void build(char *s)
	{
		last = S = ++cnt;
		for (; *s; ++s) add(*s);
	}
	void calcr(char *s)
	{
		for (int i = 0,p = S; i < n; ++i)
			++r[p = ch[p][s[i] - 'a']];
		static int b[N],t[N];
		for (int i = 1; i <= cnt; ++i) ++b[l[i]];
		for (int i = 1; i <= n; ++i) b[i] += b[i - 1];
		for (int i = 1; i <= cnt; ++i) t[b[l[i]]--] = i;
		for (int i = cnt; i; --i) r[fa[t[i]]] += r[t[i]];
	}
	void work()
	{
		for (int i = 1; i <= cnt; ++i) f[l[i]] = std::max(f[l[i]],r[i]);
		for (int i = n; i; --i) f[i] = std::max(f[i + 1],f[i]);
	}
}sam;
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("NSUBSTR.in","r",stdin);
	freopen("NSUBSTR.out","w",stdout);
	#endif
	scanf("%s",s);
	sam.build(s);
	sam.calcr(s);
	sam.work();
	for (int i = 1,n = strlen(s); i <= n; ++i) printf("%d\n",f[i]);
}