史上全网最清晰后缀自动机学习（三）后缀自动机里的树结构

时间限制:15000ms
单点时限:3000ms
内存限制:512MB
描述
小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的，小Hi想知道对
于所有的K的答案。

输入
共一行，包含一个由小写字母构成的字符串S。字符串长度不超过 1000000。

输出
共Length(S)行，每行一个整数，表示答案。

样例输入
aab
样例输出
2
1
1

hint
长度为1的子串出现次数最多的是a, 出现次数是2.
长度为2的子串出现次数最多的是aa(当然,不唯一, 也可以是ab), 出现次数是1
长度为3的子串出现次数最多的是aab,出现次数是1
所以输出
2
1
1

FOREACH State st:
	FOR i = shortest(st) .. longest(st):
    	ans[i] = max(ans[i], |endpos(st)|)

例子1:
状态8有两个儿子分别是状态3和状态7（即slink[7]=slink[3]=8)，其中endpos(3)={3}, endpos(7)={6}，
endpos(8) = {3,6}, 所以 |endpos(8)| = |endpos(3)| + |endpos(7)|, 没毛病~

例子2:
状态1有两个儿子分别是状态2和状态6，其中endpos(2)={2}, endpos(6)={5}，but endpos(1)={1,2,5}
所以 |endpos(1)| > |endpos(2)| + |endpos(6)|

结论: 对于浅粉色的节点, A是成立的, 对于绿色的节点, A是不成立的, 而要将A的叙述改成
父节点的endpos大小恰好等于所有子节点们的endpos大小之和再加1, 而且加的这个1就是父节点中的最长的那个
子串————也就是前缀S[1,...,i].

FOR i = shortest(st) .. longest(st):
    	ans[i] = max(ans[i], |endpos(st)|)

ans[maxlen(st)] = max(ans[maxlen(st)], |endpos(st)|)

FOR i = length(S) - 1 .. 1:
    ans[i] = max(ans[i], ans[i+1])

ans[4] = max(ans[4], endpos(st))

FOREACH State st:
    ans[longest(st)] = max(ans[longest(st)], |endpos(st)|) // 只更新longest的
FOR i = length(S) - 1 .. 1:
    ans[i] = max(ans[i], ans[i+1])

//#include "stdafx.h"
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
//#define LOCAL
typedef long long ll;
const int maxn = 1e6+5, SZ = 26;
int n, head[maxn<<1], cnt;
char s[maxn];
ll ans[maxn];

struct SamNode
{
	int trans[SZ], slink;
	int longest, shortest, endpos; // endpos 表示该节点的endpos集合的大小
	bool flag; // 是不是绿色节点? true表示是, false表示不是
}sam[maxn<<1];

struct Arc
{
	int from, to, nxt;
}g[maxn<<1];

void addarc(int from, int to)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from];
	head[from] = cnt++;
}

int newnode(int shortest, int longest, int *trans, int slink, bool flag)
{
	sam[n].shortest = shortest;
	sam[n].longest = longest;
	sam[n].slink = slink;
	sam[n].flag = flag;
	sam[n].endpos = sam[n].flag; // 如果是绿色节点的话, 则等于子节点的endpos之和再加1, 否则等于子节点之和
	trans?memcpy(sam[n].trans, trans, SZ*sizeof(int)):memset(sam[n].trans, -1, SZ*sizeof(int));	
	return n++;
}

int insert(char ch, int u)
{
	int c = ch - 'a';
	int z = newnode(-1, sam[u].longest + 1, 0, -1, true); // 绿色
	int v = u;
	while(~v && !~sam[v].trans[c])
	{
		sam[v].trans[c] = z;
		v = sam[v].slink;
	}
	if (!~v)
	{
		sam[z].shortest = 1;
		sam[z].slink = 0;
		return z;
	}
	int x = sam[v].trans[c];
	if (sam[x].longest == sam[v].longest + 1)
	{
		sam[z].shortest = sam[x].longest + 1;
		sam[z].slink = x;
		return z;
	}
	int y = newnode(-1, sam[v].longest+1, sam[x].trans, sam[x].slink, false); // 浅粉色
	sam[x].slink = y;
	sam[x].shortest = sam[y].longest + 1;
	sam[z].slink = y;
	sam[z].shortest = sam[y].longest + 1;
	while (~v && sam[v].trans[c] == x)
	{
		sam[v].trans[c] =  y;
		v = sam[v].slink;
	}
	sam[y].shortest = sam[sam[y].slink].longest + 1;
	return z;
}

void slinktree()
{
	memset(head, -1, sizeof(head));
	for (int i = 1, to; i < n; i++)
	{
		to = sam[i].slink;
		if (~to)
		{
			addarc(to, i);
		}
	}
}

void dfs(int cur)
{
	for (int h = head[cur], to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		dfs(to);
		sam[cur].endpos += sam[to].endpos;
	}
}

inline void mmax(ll &a,ll b)
{
	if (a<b)
	{
		a = b;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%s", s+1);
	int u = newnode(0,0,0,-1, true),i = 1, len = strlen(s+1);
	while(s[i])
	{
		u = insert(s[i], u);
		++i;
	}
	slinktree(); // 利用反向slink弧构建slink树
	dfs(0); // 树上dfs求所有节点的endpos
	for (int i = 1;i<n; i++)
	{
		mmax(ans[sam[i].longest], sam[i].endpos);
	}
	for (int i = len - 1; i; i--)
	{
		mmax(ans[i], ans[i+1]);
	}
	for (int i = 1;i<=len; i++)
	{
		printf("%lld\n", ans[i]);
	}
	return 0;
}

Accepted