前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >史上全网最清晰后缀自动机学习(三)后缀自动机里的树结构

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

作者头像
ACM算法日常
发布2019-12-23 17:38:23
1.1K0
发布2019-12-23 17:38:23
举报
文章被收录于专栏:ACM算法日常

缘起

【1】+【2】我们已经入门了后缀自动机, 并且给出了后缀自动机 O(n) 的构造算法. 现在继续前行. hihocoder #1449 : 后缀自动机三·重复旋律6

分析

代码语言:javascript
复制
时间限制: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

本题是SAM的运用. 通过【1】的学习, 我们知道了一个字符串S的后缀自动机其实是一部用于识别S的所有子串的机器, 而且通过【2】进一步的学习, 我们知道如果一个字符串不是S的子串的话, 则将其一个字符一个字符的喂进SAM中的话, 则将必定在喂入某个字符的时候出现无路可走的情况(即喂入字符c, trans[c]=null, 而不能正确的转移到sam的某个节点去). 换言之, 文本串S的后缀自动机是一部恰好只能识别S的全部子串的机器!

那本题该如何求解呢? 毫无疑问, 先构建S的sam. 我们首先断言, 如果能求出sam中每个节点的enspos集合的大小, 那么此题至少有如下暴力解法. 因为我们完全可以写出如下伪代码

代码语言:javascript
复制
FOREACH State st:
	FOR i = shortest(st) .. longest(st):
    	ans[i] = max(ans[i], |endpos(st)|)

其中ans[i] 表示出现次数最多的长度为i的子串的出现次数. 复杂度是O(N^2)的. 至于如何优化, 我们后面再说. 先至少保证能写出这个暴力算法来. 后面再优化复杂度.

那么SAM的每个节点的endpos的大小怎么求出来呢? 我们还是以 S="aabbabd" 为例, 它的SAM如下(这个在【1】中已经画过了)

image

然后我们将trans去掉, 仅仅考虑slink. 则我们发现SAM在slink下形成了一棵以起点0为根的树(一定是一棵有根树, 因为回想一下【1】中slink是怎么形成的? 不就是不断的删掉字符最终删光了走到节点0么? ).

然后各个节点如下

状态

子串

endpos

S

空串

{0,1,2,3,4,5,6,7}

1

a

{1,2,5}

2

aa

{2}

3

aab

{3}

4

aabb,abb,bb

{4}

5

b

{3,4,6}

6

aabba,abba,bba,ba

{5}

7

aabbab,abbab,bbab,bab

{6}

8

ab

{3,6}

9

aabbabd,abbabd,bbabd,babd,abd,bd,d

{7}

注意, 图2中除了起点0之外, 其余的9个顶点被着以两种颜色——一种是浅粉色, 一种是绿色. 绿色的节点表示是【2】中代码第28行新建的节点z——即S[1,...,i+1]所属的节点(【2】中的附录图1中的z), 换言之是每次新读入字符产生的新的前缀属于的节点. 而浅粉色的节点是【2】中代码48行从x拆分出来的y(【2】中的附录图3中的y), 换言之, 是拆分出来的节点. 也就是S的sam节点的个数>=S的长度. 多出来的都是拆分出来的节点. 例如上图中的5和8就是就是拆分出来的节点.

很明显的事情是, 绿色的节点中一定包含前缀, 而且前缀就是该节点中最长的那个子串(根据【2】的代码就知道).而浅粉色节点中一定不包含前缀, 因为浅粉色的节点(即【2】中的y)是【2】中的u=S[1,..,i]不断的删除前面的字符走到的节点v然后再读入S[i+1]这个字符产生的节点. 既然已经删掉了一些前面的字符, 当然不可能是前缀啦~

因为刚刚说了, sam用slink已经形成了一棵有根树. 所以我们寻思着能不能构造完毕sam之后, 再自底向上递归地将每个 顶点的endpos大小求出来. 我们想当然的认为 父节点的endpos大小恰好等于所有子节点们的endpos大小之和 (下面简称这个断言为A). 然鹅, 事实上, 这是不正确的.

代码语言:javascript
复制
例子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)|

所以父节点的enpos大小=子节点们的endpos大小之和并不成立! 那是不是我们不能利用上面优美的树形结构了呢? 非也, 非也, 情况事实上没有辣么的糟糕!

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

为什么上面的结论对呢? 首先根据【1】的引理, 我们知道父节点的诸多子节点之间是不可能endpos交非空的. 否则这些子节点之间就存在后缀关系, 这些子节点之间就会存在slink关系. 就不会是兄弟关系了. 其次, 如果父节点的endpos中存在一个不在任何子节点的endpos中出现的值, 假设这个值是q, 并且产生这个q的父节点中的子串是sub = S[p,..,q], 则如果p>1(浅粉色节点)的话, 可以想象sub一定会属于某个子节点的! 除非p=1(绿色节点), 即产生这个q的是一个前缀! 那么根据我们sam的构造算法, 就不可能属于任何一个子节点!

这就是为什么我们要区分浅粉色节点和绿色节点的理由!

那么既然是树上的递归, 我们还有一个要考虑的问题就是叶子节点的值是多少? 我们说 ,叶子节点的endpos大小一定是1. 因为节点就只有浅粉色和绿色两种, 而浅粉色节点是拆分出来的节点, 根据【2】中的构造算法, 浅粉色的节点一定不可能是叶子. 所以叶子只可能是绿色节点(简称绿叶). 绿叶一定不可能endpos的大小>1, 否则说明绿叶中最长的那个子串——即前缀S[1,...,i]出现次数>1——即不仅仅在i处出现, 还在j处出现, 显然j>i. 那么考虑S[1,..,j]所在的节点. 则不难知道此绿叶必定不是叶子节点了. 所以叶子的endpos的大小一定是 1

至此, 我们知道了如何得到每个sam节点中的endpos大小的算法.

  1. 构建sam. sam节点中除了sam必须的trans、slink之外,还需要shortest(因为本题和子串长度有关)、longest、endpos(endpos的大小)、flag (是不是绿色节点,true表示是)这4个业务字段.
  2. 类似于ac自动机构造fail树. 构造完sam(或者构造sam途中)之后我们也要使用反向slink构造slink树——一棵以0为根节点的树. 即类似于ac自动机和fail树之间的关系是: 节点都是那些节点,只是节点组织的形式不一样, ac自动机靠的是trie, 而fail树靠的是反向fail指针. 后缀自动机和slink树的关系是: 节点也都是那些节点, 只是节点组织的形式不一样, 后缀自动机靠的是trans, 而slink树靠的是反向slink指针.
  3. slink树的叶子的endpos=1. 然后在slink树上递归, 求出所有sam节点的endpos字段的值.

注意, 上面三步的复杂度是O(N)的. 而且因为自动机的节点数至多2N个, 所以不难知道上面三步算法的常数比较小. 是很优秀的.

那么怎么得到答案呢? 如果使用本文开头的暴力算法的话, 复杂度堕入O(n^2) 那岂不是迄今为止slink树的努力全部白费了? 非也非也!

对于每个节点, 我们不需要去更新节点所有的子串对应长度的答案, 也就是我们不需要对每个节点执行下面的O(n)伪代码

代码语言:javascript
复制
FOR i = shortest(st) .. longest(st):
    	ans[i] = max(ans[i], |endpos(st)|)

只需要更新节点中的longest对应的答案就行了. 即对每个节点, 只需要执行下面的O(1)伪代码即可

代码语言:javascript
复制
ans[maxlen(st)] = max(ans[maxlen(st)], |endpos(st)|)

然后注意到ans[1], ans[2], ... ans[length(S)]一定递减(因为一个长度为i的子串出现了, 则长度为i-1、i-2、...、1的子串一定也都出现了). 所以我们只需要继续

代码语言:javascript
复制
FOR i = length(S) - 1 .. 1:
    ans[i] = max(ans[i], ans[i+1])

即可。还是以 S="aabbabd"为例. 我们要求 ans[4]. 那么根据上面的表格, 我们知道长为4的子串在4、6、7、9 这四个节点中出现过. 所以按道理, ans[4]应该在遍历4、6、7、9这4个状态的时候, 对于每个状态st, 来一次

代码语言:javascript
复制
ans[4] = max(ans[4], endpos(st))

这个过程就是文初的O(n^2)暴力算法. 但是其实没必要. 因为例如 abba 这个长度为4的子串在6这个状态出现过. 但是它的endpos和longest(6) = aabba 是一毛一样的! 所以我们只需要得到 ans[5]即可. 然后用ans[5]来max化 ans[4].

综上所述, 我们应该使用下面的伪代码来完成对答案的计算

代码语言:javascript
复制
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])

上述伪代码的复杂度是O(n)的.

好了, 说了这么多, 来愉快的切代码吧~

代码语言:javascript
复制
//#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;
}

ac情况

代码语言:javascript
复制
Accepted

参考

【1】《史上全网最清晰后缀自动机学习(一)基本概念入门》

【2】《史上全网最清晰后缀自动机学习(二)后缀自动机的线性时间构造算法》

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-12-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 缘起
  • 分析
  • 参考
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档