hdu 3518 Boring counting 后缀树

缘起

借本题我们讲解了后缀树这种数据结构,. 所以找到了 hdu 3518 Boring counting 来练习一下.

分析

题意是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
035现在面临一个棘手的问题，他的英语老师给了他一个字符串，其中包含n个小写字母，他必须弄清楚有多少子串出
现至少两次，而且，重复子串不能有相互重叠。
以aaaa为例。“a”apears四次，“aa”apears两次没有重叠。但是，aaa不能超过一次而没有重叠。因为我们可以从
[0-2]得到“aaa”,也可以从[1-3]得到"aaa"。 但是[0-2]和[1-3]有重叠。所以“aaa”不能计入结果.
因此，答案是2（“a”和“aa”）。

【输入】
输入数据由几个测试用例组成。输入以“＃”行结束。每个测试用例包含一个由小写字母组成的字符串，长度n不超过
1000（n <= 1000）。

【输出】
对于每个测试用例输出一个整数ans，它代表测试用例的答案。你最好使用int64来避免不必要的麻烦。

【样例输入】
aaaa
ababcabb
aaaaaa
#

【样例输出】
2
3
3

【限制】
Time limit 1000 ms
Memory limit 32768 kB

本题的思路就是先使用给定的字符串拼上 $ 之后 建立后缀树, 然后在后缀树上进行dfs.

我们首先介绍本文的主角——后缀树. 后缀树又叫做后缀trie. 即将一个字符串拼上一个不在这个字符串中出现的字符（特别的，我们取’{‘）之后，它的所有后缀构成的字符串构成的压缩trie. 例如 XMADAMYX 的后缀树如下

​ 图1

构建S的后缀树显然不能使用构造压缩trie的方式进行暴力构造——因为那样的算法是O(n^2)的. 本文介绍O(n)构造后缀树的Ukkonen（以下简称ukk）算法.

ukk算法网上介绍很多，但是很多代码实现都是错的（我很好奇，我要是他们，学习了一个数据结构之后，一定会找一道板题来测一下, 不测一下自己写的板子就网上贴算怎么回事?）

ukk算法的过程就是每次读入一个字符. 例如 “abcabxabcd”, 第一次读入 “a”（其实表示插入后缀 [0,11)）

第二次读入 “b” （表示插入后缀[1, 11)）, 第三次读入 “c” （表示插入后缀 [2,11)）, 最后读入 ‘{‘ （表示读入后缀 [10,11)）. 所以要想O(n)时间完成后缀树的构建就需要每次插入都是 O(1) 时间完成. 所以理想的情形是有一个数据结构A能维护下一次要插入的位置. 这样下一次插入的时候，我们根据A就能O(1)找到插入的位置，然后插入即可. 所以ukk算法的核心就是这个A(代码中的cur)，而维护这个A需要一个后缀链接（即代码中的link）来高效维护.

下面以一种意识流的方式讲解后缀树的构建方法. 并且讲解过程完全就是后面代码的过程

假设我们已经读入了前i个字符，也就是插入了 S[0,..,i-1], 则可以知道这i个后缀已经全部在后缀树中了. 下面读入字符 Si, 假设隐式读入的字符索引在Sm

1
2
3
（所谓隐式读入，例如i=3读入S3='a'， 但是后缀树中已经有'以a'开头的后缀了（S0='a'开头的后缀就是）, 则m
就=3不增加了，表示我们没有显式插入后缀[3,11)，则下次i=4的时候, 读入S4='a'的时候, 我们的j其实从j=m=3
开始, 表示我们要插入的后缀是S3S4和S4，为什么要带上S3? 因为S3在上一步没有显式插入啊）

则此次要插入的后缀是 S[m,…,i],.,,,S[i,i]

首先要插入 S[m,…,i]：根据A，O(1)时间找到插入的位置pos. 然后看看w[pos]和要插入的字符是否相等? 如果相等，则继续隐式插入，S[m,..,i]一直到S[i,i] 都不需要显式插入了（因为S[m…,i]都隐式插入了，而因为S[m-1,…,i-1]肯定存在后缀树中，所以S[m-1,…,i]肯定也可以隐式插入后缀树, 所以本步骤可以结束了，不需要继续进行下去了）. 如果不相等，就会产生分裂，分裂的结果就是我们已经显式插入了后缀 S[m,…,i] 然后考虑插入后缀 S[m+1,…,i] 而我们知道S[m+1,…,i-1]是已经存在后缀树中了. 所以我们需要快速(O(1)时间)找到该后缀在后缀树中的位置. 这就是后缀链接link的用武之地. 如果S[m,..,i-1] 存在后缀链接的话, 直接用后缀链接跳就可以了, 如果没有的话（link为NULL），则需要自己找了，也就是使用S[m+1,…,i) 从root开始走（也就是代码中的find_node）.找到了就可以考虑为后缀S[m+1,…,i-1]插入S[i]了（该分裂分裂，该隐式插入隐式插入）. 前后两次相邻发生的分裂，前面发生分裂的节点需要将其link指向后面发生的分裂的节点， 这是后缀链接的构造——用于快速定位下次插入的位置.

下面我们考虑本题的场景——要统计至少不重复的出现2次的子串的个数. 我们记符合条件的字符串为p, 我们知道，任何一个子串都是一个后缀的前缀. 所以p一定会终结于后缀树上的某个节点处. 而p能不重叠的出现2次（以上），假设出现的两次分别为p1和p2, 例如

​ 图2

则 |L1-L2|>=|p|, 其实这也是充要条件. 也就是

1
p能不重叠的至少在S中出现2次的充要条件是p的所有到达字符串末尾最远距离减去最近距离>=p的长度

而将图1放在后缀树中看的话, 就是下面这个样子

​ 图3

所以要解决问题的话, 就只需要在后缀树上dfs. 对于后缀树上每个节点, 通过dfs找到它到叶子需要经历的最少字符数（最长字符数是不需要dfs的, 因为就是n+1-p->e, n是字符串的长度, +1是因为我们把 $ 也算进来了）

然后就可以计算出该节点上满足条件的后缀数量了.

​ 图4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include "stdafx.h"
#define LOCAL
#include <string.h>
#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
const int MAX_N=1005, SIZE = 27, MAX_NODE = 10000, _min=0x3f3f3f3f; // MAX_N 是单词的最大长度, SIZE是孩子节点的个数, MAX_NODE是后缀树节点的最大个数
char w[1005];

typedef struct SuffixTreeNode
{
	int s,e,num,len; // 本节点表示 w[s,e), 从根节点到此节点的字符串长度为num, e-s=len
	SuffixTreeNode *next[SIZE]; // 孩子指针
	SuffixTreeNode *parent,*link; // 父节点, 后缀链接
	void clear() {memset(next, 0, sizeof(next));}
	SuffixTreeNode *find_node(int j, int i, int &pos) // 其实只有root会调用这个方法, 此方法是寻找w[j,...,i)从root出发,找插入的位置
	{
		if (i==j)
		{
			pos = 0;
			return this;
		}
		SuffixTreeNode *p = this->next[w[j]-'a'];
		pos = p->s;
		while(p->e-p->s<i-j) // 只要当前节点满足不了
		{
			j+=(p->e-p->s); // 就减掉这么多实现越过当前节点p这个效果
			pos = p->e;
			p = p->next[w[j]-'a'];
			pos = p->s;
		} // 最后 i-j 可以被 p=w[s,e) 吃住了
		pos += (i-j);
		return p;
	}
}SuffixTreeNode, *SuffixTree;

SuffixTreeNode nodes[MAX_NODE]; // 节点数组, 相当于是一块内存池, 则不需要new了(new比较慢，不如这样一开始就开辟一片来得快)
int nodecount, count, n; // nodecount是节点个数, count 是答案, n是字符串w的长度

SuffixTree root;

SuffixTree new_node(int s, int e, SuffixTree parent) // 新建一个节点
{
	SuffixTree p = &nodes[nodecount++];
	p->s = s, p->e = e;
	p->clear();
	p->link = 0;
	p->parent = parent;
	return p;
}

int dfs(SuffixTree p) // 返回p为根节点的后缀子树到所有叶子的最短字符数量, 注意, 字符数量不包含p本身.
{
	if (p->e==n+1) // 如果已经是叶子
	{
		return 0;
	}
	int ans = _min;
	for (int i = 0; i<SIZE; i++)
	{
		if (p->next[i])
		{
			p->next[i]->len = p->next[i]->e-p->next[i]->s; // 这个没写进ukk算法, 因为ukk只是单纯构建后缀树(len并不是ukk算法必须的字段), 不要写进无关的代码
			p->next[i]->num = p->next[i]->len + p->num; // 计算出从根节点到本节点(本节点需要完结)的字符数量
			int ret = dfs(p->next[i]);
			if (ret + p->next[i]->len<ans)
			{
				ans = ret + p->next[i]->len;
			}
		}
	}
	// 求出了p到叶子经历的最短字符数量
	int t = (n-p->e+1)-ans; // p到叶子经历的最多字符数量减去最少数量
	if (p!=root && p->num-t<p->len) // 是这样推导的：p->num-x<=t &&  0<=x<p->len, 可得满足条件的x的个数
	{
		count += p->len - MAX(0, p->num-t);
	}
	return ans;
}

void ukk() 
{
	nodecount = 0;
	root = &nodes[nodecount++];
	root->s = root->e = 0;
	root->parent = root->link = 0;
	root->clear();
	n = strlen(w);
	w[n] = '{';
	w[n+1] = 0;
	SuffixTree cur = root;
	for (int i =0, m =0, pos = 0 ; i<=n;i++) // 依次加入字符 w[i], pos 是下一个插入的位置, 这是在w中的索引, 即要和w[pos]匹配的话, 就不需要显式分裂
	{
		SuffixTree last = 0;
		for (int j = m; j<=i; j++) // 要加入的后缀是 w[j,...,i], m<=j<=i
		{
			if (last) // 第一次就不能依据后缀链接进行跳跃
			{
				if (cur->link) // 如果有后缀链接, cur就要继续沿着后缀链接进行变化
				{
					cur = cur->link;  // 就按照后缀链接进行跳跃, 即找 [j,...,i) 这个后缀对应的节点
					pos = cur->e;
				}
				else // 如果没有后缀链接
				{
					cur = root->find_node(j, i, pos); // 就只能从根节点出发寻找插入的位置
				}
			}
			if (pos<cur->e) // 如果插入可以在cur上进行
			{
				if (w[i]==w[pos]) // 隐式插入
				{
					pos++;
					break;
				}
				else // 显式插入（分裂）,见图4
				{
					SuffixTree internal = new_node(cur->s, pos, cur->parent); // 内部节点
					cur->parent->next[w[cur->s]-'a'] = internal; // internal取代cur作为cur的父亲的儿子.
					cur->s = pos;
					cur->parent = internal;
					internal->next[w[i]-'a'] = new_node(i, n+1, internal); // w[i] 和 w[pos] 分道扬镳,分裂出2个节点
					internal->next[w[pos]-'a'] = cur;
					cur = internal;
				}
			}
			else // 则插入只能在cur的后一个节点进行
			{
				if (cur->next[w[i]-'a']) // 隐式插入
				{
					cur = cur->next[w[i]-'a']; // 则要跑到cur->next[w[i]-'a']上去插了
					pos= cur->s+1;
					break;
				}
				else // 显式插入
				{
					cur->next[w[i]-'a'] = new_node(i,n+1, cur);
				}
			}
			if (last)
			{
				last->link = cur;
			}
			last = cur;
			m++;
		}
	}
}


int main(){
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while (scanf("%s", w) , w[0] != '#')
	{
		count = 0;
		ukk(); // 线性时间构造后缀树
		root->len = root->num = 0;
		dfs(root);
		printf("%d\n", count);
	}
	return 0;
}

ac结果

30127980 2019-08-06 13:20:21 Accepted 3518 15MS 1540K 4351 B G++ yfsyfsyfs

最后分享一个比较好的老外菊苣做的后缀树动画展示网站 Visualization of Ukkonen’s Algorithm

大家可以用它来验证自己写的后缀树算法是否正确. 但是它的算法具体步骤和我实现的略有不同.