poj 3461 Oulipo 后缀树 KMP

缘起

再也不水题了~ 立个flag, 潜心要搞定 字符串和各种平衡树（啥树套树、替罪羊、主席树、树剖啥的）~ 首先拿字符串开刀. 字符串算法其实贼难了~ 然后最近学习后缀树. 【1】中其实敲了一个后缀树 ukk的板子。 现在用它来找题来切. 但是无奈网上用后缀树切的题不多（大部分都是后缀数组）. 所以我找到【2】中说的后缀树的四大运用。来逐个找题切来提高对后缀树的理解. 首先从kmp板题 poj 3461 Oulipo 开始吧~

分析

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
给一个子串再给一个主串，问子串在主串中出现了多少次。

【输入】
多样例. 每个样例如下的输入格式
一行是模式串, 一行是文本串. 模式串的长度<=1w, 文本串的长度<=100w

【输出】
对于每个样例, 输出出现的次数

【样例输入】
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

【样例输出】
1
3
0

【限制】
1s

本题虽然可以是kmp裸题, 但是还是想学习一下后缀树. 后缀树如何解决精确匹配问题在【2】中已经说的很清楚了。用文本串构造后缀树，按在trie中搜索字符串的方法搜索模式串即可——先定位，再计算后缀子树的叶子数量即可。 原理是若模式串在文本串中的话，则模式串必然是文本串的某个后缀的前缀.

下面的代码和【1】相比，将后缀树的板子改的更加简练了一些.

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
165
166
167
168
169
170
171
172
173
174
175
176
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define LOCAL

const int SIZE = 27, maxs = 10005, maxt = 1000005;
char s[maxs], t[maxt];
int ans, n,count;

typedef struct SuffixTreeNode
{
	int s,e;
	SuffixTreeNode *next[SIZE], *parent, *link;
	
}SuffixTreeNode, *SuffixTree;

SuffixTreeNode nodes[maxt<<2];

SuffixTree root;

SuffixTreeNode *find_node(int j, int i, int &pos) // 和【1】不同,我把该方法拆出来了——反正只有root调
{
	if (i==j)
	{
		pos = 0;
		return root;
	}
	SuffixTreeNode *p = root->next[t[j]-'A'];
	pos = p->s;
	while(p->e-p->s<i-j)
	{
		j+=p->e-p->s;
		p = p->next[t[j]-'A'];
		pos = p->s;
	}
	pos+=i-j;
	return p;
}

SuffixTree newnode(int s, int e, SuffixTree parent) // 内存池取出一个节点
{
	SuffixTree p = &nodes[count++];
	p->s = s, p->e = e;
	memset(p->next, 0, sizeof(p->next));
	p->link = 0;
	p->parent = parent;
	return p;
}

void ukk()
{
	count = 0;
	root = newnode(0,0,0);
	n = strlen(t);
	t[n] = '[';
	t[n+1]=0;
	SuffixTree cur = root; // ukk算法初始化
	for (int i = 0, m=0,pos=0; i<=n; i++) // 其实整个ukk最重要的就是(cur,pos), cur描述了在哪个节点上插, pos描述了在cur这个节点的哪个位置上插
	{
		SuffixTree last = 0;
		for (int j = m; j<=i; j++) // 其实每次因为读入了新的字符 t[i], 所以插入的后缀都是t[j,..,i], j不一定跟得上i的步伐, 因为可能出现隐式插入导致m并不会++
		{
			if (last)
			{
				if (cur->link)
				{
					cur = cur->link;
					pos = cur->e;
				}
				else
				{
					cur = find_node(j,i,pos);
				}
			}
			if (pos<cur->e) // 观察find_node方法, pos可能=cur->e的,而每个节点表示的是[s,e), 所以其实要跑到cur的后一个节点去插的
			{
				if (t[i]==t[pos])
				{
					pos++;
					break;
				}
				else
				{
					SuffixTree inter = newnode(cur->s, pos, cur->parent);
					cur->parent->next[t[cur->s]-'A'] = inter;
					cur->s = pos;
					cur->parent = inter;
					inter->next[t[i]-'A'] = newnode(i,n+1,inter);
					inter->next[t[pos]-'A'] = cur;
					cur = inter;
				}
			}
			else // 新增节点可能要跑到cur的后继节点去(因为pos=cur->e)
			{
				if (cur->next[t[i]-'A']) // 隐式插入
				{
					cur = cur->next[t[i]-'A'];
					pos = cur->s+1;
					break;
				}
				else // 显式插入
				{
					cur->next[t[i]-'A'] = newnode(i, n+1, cur);
				}
			}
			if (last)
			{
				last->link = cur;
			}
			last = cur;
			m++; // 可能因为上面的break（即隐式插入）而导致m并不会和i同步增长
		}
	}
}

SuffixTree locate() // 根据模式串s定位到后缀树上某个节点,这个地方比较容易出错,要小心
{
	SuffixTree cur = root;
	int i = 0;
	while(s[i])
	{
		if (cur->next[s[i]-'A'])
		{
			cur = cur->next[s[i]-'A']; // 跑到cur上去比较
			int j = cur->s;
			while(j<cur->e && t[j]==s[i]) // s+i和t[cur->s, cur->e) 比较
			{
				i++, j++;
			}
			if (j<cur->e && s[i]) // 则该模式串在该文本串中不出现, 注意, 每个节点表示的范围是[s,e)
			{
				return 0;
			}
		}
		else // 分支都没有,模式串肯定不会出现
		{
			return 0;
		}
	}
	return cur;
}

int dfs(SuffixTree cur) // 计算cur为根节点的子树中叶子节点的个数, 简单的递归
{
	if (cur->e==n+1) // 如果cur是叶子节点
	{
		return 1;
	}
	int ans = 0;
	for (int i = 0;i<SIZE; i++)
	{
		if (cur->next[i])
		{
			ans+=dfs(cur->next[i]);
		}
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%s%s", s,t);
		ans = 0;
		ukk();
		SuffixTree p = locate();
		printf("%d\n", p?dfs(p):0);
	}
	return 0;
}

但是遗憾的是, 该程序提交直接MLE掉了（但是和ac代码对拍过, 算法没有给出错误答案）. 原因也很简单——后缀树太吃内存了. 这也是后缀树的一个缺点. 不仅编码有一定的复杂度, 而且吃内存.

最后，虽然【1】中已经给出过ukk算法的原理. 但是这里再讲一次.

其实, ukk O(n) 建树的核心正如上面注释写的那样——就是cur和pos. 而初学者（比如我~）比较容易困惑的事情是last->link=cur这件事情. 其实【1】中也是说清楚了的. 随着读入字符t[i], 则要插入的后缀是t[j,..,i]（注意, 并不是到了\$, 这里是读入一个字符t[i]就假想它就是最后那个字符的）, 其中 m<=j<=i, 其中m可能<i, 这是因为隐式插入导致的. 而插入后缀 t[j,..,i] 不就是在之前已经在后缀树中的 t[j,…,i-1]后面加一个t[i]吗? 所以我们只需要快速（即O(1)时间）在后缀树中定位到之前插入的 t[j,…,i-1] 这个后缀就好啦~ 这就是后缀树中的cur（包括了link）+pos的作用.

link（即有些文章讲的后缀链接）加速就是节点t[j-1,…,i-1] 到 节点t[j,..,i-1] 的链接, 因为前者不就比后者多一个字符[j-1]么? 例如前者为abc、后者为bc, 则前者比后者多一个a, 如果有abc到bc的后缀链接的话, 则下次插入一个d, 则abc插完之后，即插完t[j-1,…,i], 其中t[i]就是d, 之后, 想插 t[j,..,i], 则根据abc的后缀链接很快就能找到bc的位置进行插入, 这就是link加速

那么代码中last->link=cur是什么意思呢? 从代码不难看到last其实就是前一次的cur. 而代码61行，即

1
for (int j = m; j<=i; j++)

就是插入一个字符t[i]（即刚刚举的小例子中的d）然后我们要考察之前因为隐式插入而没有显式插入的所有后缀t[m,…,i-1],…,t[i-1,i-1] 因为拼上了 t[i] 之后变成了 t[m,…,i],…,t[i-1,i], t[i,i] 看看是不是会变成显式插入而产生新的后缀树节点. 这个时候, 在上一轮for循环（即代码61行）中在 t[m,…,i-1],…,t[i-1,i-1] 之间形成的link链接（这不就是上一轮for循环中的last->link=cur形成的吗?）就起到了加速的作用，好吧，我再说一次. 这次意识流一点. 当前for循环（即代码61行的for循环）不就是要在 t[m,…,i-1],…,t[i-1,i-1] 后面都拼上t[i]们形成了新的后缀然后看看是不是依旧还是隐式插入吗? 好，如果隐式插入了，则break. 则61行for循环结束. m不再++了. 故事结束, 反之, 如果形成了显式插入的话，例如 t[j-1,…,i-1,i] 形成了显式插入. 则就不会break, 然后我们要考察t[j,…,i-1,i]是否能显式插入. 而t[j,..,i-1,i] 不就是 t[j,…,i-1]（上一轮for循环留下的隐式插入的后缀）再拼上t[i]吗? 所以快速（O(1)时间）找到t[j,…,i-1]对于ukk算法的性能至关重要. 而如果t[j-1,…,i-1] 这个节点（注意，这个就是当前for循环刚刚显式插入完毕的cur节点）到t[j,…,i-1]有link链接的话, 则我们一步就能定位到要处理的t[j,…,i-1]，然后考察它拼上t[i]——该显式插入显式插入，该隐式插入隐式插入，如此云云~ 而这个link是上一次for循环last和cur产生的呀~ 所以就知道

1
last->link=cur, last=cur

last不就是 t[j-1,…,i-1]么? cur不就是 t[j,..,i-1]么? 然后此行代码形成了last到link的后缀链接.

聪明如你四不四已经体会到了ukk的美妙了呢? 哈哈哈~ 欢迎拍砖~

参考

【1】https://yfsyfs.github.io/2019/08/03/hdu-3518-Boring-counting-后缀树/

【2】https://blog.csdn.net/f81892461/article/details/8643974