缘起
借本题我们讲解了后缀树这种数据结构,. 所以找到了 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;
char w[1005];
typedef struct SuffixTreeNode
{
int s,e,num,len;
SuffixTreeNode *next[SIZE];
SuffixTreeNode *parent,*link;
void clear() {memset(next, 0, sizeof(next));}
SuffixTreeNode *find_node(int j, int i, int &pos)
{
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);
pos = p->e;
p = p->next[w[j]-'a'];
pos = p->s;
}
pos += (i-j);
return p;
}
}SuffixTreeNode, *SuffixTree;
SuffixTreeNode nodes[MAX_NODE];
int nodecount, count, n;
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)
{
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;
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;
}
}
}
int t = (n-p->e+1)-ans;
if (p!=root && p->num-t<p->len)
{
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++)
{
SuffixTree last = 0;
for (int j = m; j<=i; j++)
{
if (last)
{
if (cur->link)
{
cur = cur->link;
pos = cur->e;
}
else
{
cur = root->find_node(j, i, pos);
}
}
if (pos<cur->e)
{
if (w[i]==w[pos])
{
pos++;
break;
}
else
{
SuffixTree internal = new_node(cur->s, pos, cur->parent);
cur->parent->next[w[cur->s]-'a'] = internal;
cur->s = pos;
cur->parent = internal;
internal->next[w[i]-'a'] = new_node(i, n+1, internal);
internal->next[w[pos]-'a'] = cur;
cur = internal;
}
}
else
{
if (cur->next[w[i]-'a'])
{
cur = 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结果
最后分享一个比较好的老外菊苣做的后缀树动画展示网站 Visualization of Ukkonen’s Algorithm
大家可以用它来验证自己写的后缀树算法是否正确. 但是它的算法具体步骤和我实现的略有不同.