【SPOJ 8222】Substrings

http://www.spoj.com/problems/NSUBSTR/

clj课件里的例题

用结构体+指针写完模板后发现要访问所有的节点，改成数组会更方便些。。于是改成了数组。。。

这道题重点是求一个状态的\(|Right|\)值，只要用parent树中当前节点的所有孩子来更新它即可。

为了保证一个节点的parent一定被所有孩子全部更新，需要保证在序列中一个节点的parent一定在它的左边(从右往左扫来更新)。

这就需要对\(val\)值排序，因为spoj时限卡得紧，所以用基数排序。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1000003;

int val[N], par[N], go[N][26], tot = 1, root = 1, last = 1;

void extend(int w) {

	int p = last, np = ++tot;

	val[np] = val[p] + 1;

	while (p && go[p][w] == 0)

		go[p][w] = np, p = par[p];

	if (p == 0) par[np] = root;

	else {

		int q = go[p][w];

		if (val[p] + 1 == val[q]) par[np] = q;

		else {

			int nq = ++tot; val[nq] = val[p] + 1;

			memcpy(go[nq], go[q], sizeof(go[q]));

			par[nq] = par[q];

			par[q] = par[np] = nq;

			while (p && go[p][w] == q)

				go[p][w] = nq, p = par[p];

		}

	}

	last = np;

}

int len, r[N], a[250003], id[N], c[250003], f[250003];

char s[250003];

int main() {

	scanf("%s", s + 1);

	len = strlen(s + 1);

	for(int i = 1; i <= len; ++i)

		a[i] = s[i] - 'a', extend(a[i]);

	int tmp = root;

	for(int i = 1; i <= len; ++i) {

		tmp = go[tmp][a[i]];

		r[tmp] = 1;

	}

	for(int i = 1; i <= tot; ++i)

		++c[val[i]];

	for(int i = 1; i <= len; ++i)

		c[i] += c[i - 1];

	for(int i = 1; i <= tot; ++i)

		id[c[val[i]]--] = i;

	for(int i = tot; i >= 1; --i)

		r[par[id[i]]] += r[id[i]];

	for(int i = 1; i <= tot; ++i)

		f[val[i]] = max(f[val[i]], r[i]);

	for(int i = len; i >= 1; --i)

		f[i - 1] = max(f[i], f[i - 1]);

	for(int i = 1; i <= len; ++i)

		printf("%d\n", f[i]);

	return 0;

}