学数据结构导致的
前缀函数
首先我们需要实现一个前缀函数 next(i)
在这个实现当中，next(i) 表示在
的子串的最大前后缀子串相同长度，形式化的 ，对于 有
事实上这个 next(i)
表示的是最长相同前后缀子串的后一个字符的位置
朴素实现
我们一般会把这个函数以数组的形式存起来便于访问，这个函数的一个朴素实现如下
1
2
3
4
5
6
7
8
9
10
11
12
| vector<size_t> prefix_function(string p) {
vector<size_t> next(p.size(), 0);
for (int i = 2; i < (int)p.size(); i++) {
for (int j = i - 1; j > 0; j--) {
if (p.substr(0, j) == p.substr(i - j, j)) {
next[i] = j;
break;
}
}
}
return next;
}
|
容易看出，这个算法的时间复杂度是 ，这是因为外层的两个 for
执行是
的，而内层的 substr 的比较是
基本优化
在这个基础上我们容易发现， 最多为 ，因此一个容易的优化可以这样实现
1
2
3
4
5
6
7
8
9
10
11
12
| vector<size_t> prefix_function(string p) {
vector<size_t> next(p.size(), 0);
for (int i = 2; i < (int)p.size(); i++) {
for (int j = next(i-1) + 1; j > 0; j--) {
if (p.substr(0, j) == p.substr(i - j, j)) {
next[i] = j;
break;
}
}
}
return next;
}
|
可以证明这个算法的时间复杂度是
而在这个的基础上，我们还可以有另一个观察，当计算 时，如果 ，那么
而当 时，我们则考虑不断的找一个更小的
，同时我们检测 与 是否相等，若相等我们就找到了
，否则我们一直这样下去，直到 ，若这时仍不满足则认为
而在这里我们还有一个观察，因为
我们已经找到，因此这时有 ，而我们找到的更小的一个 则意味着有
，注意到 ，这是因为本身较大的一段前后缀子串相等，那么较小的一段的后缀子串也与较大的一段子串的前缀的后部相等，而较小的一段的后缀字串与它的前缀相等，那么
，这即是在找
因而我们有递推式
因而我们可以写出算法
1
2
3
4
5
6
7
8
9
10
| vector<size_t> prefix_function(string p) {
vector<size_t> next(p.size(), 0);
for (size_t i = 2; i < p.size(); i++) {
size_t j = next[i - 1];
while (j > 0 && p[i - 1] != p[j]) j = next[j - 1];
if (p[i - 1] == p[j]) j++;
next[i] = j;
}
return next;
}
|
可以证明，这个算法是 的，这是因为 每一轮 for
循环最多递增一次，因此 ，而 while 循环中的 虽然不断减少，但是总有 ，因此对于总的 更新次数也有 ，因此总的时间复杂度是
朴素的字串匹配算法
1
2
3
4
5
6
7
8
9
10
11
| int naive_indexOf(string p, string s) {
for (size_t i = 0; i < s.size(); i++) {
for (size_t j = 0; j < p.size(); j++) {
if (s[i + j] != p[j])
break;
else if (j == p.size() - 1)
return i;
}
}
return -1;
}
|
容易看出，这是一个
的算法，效率并不高，我们可以和发现，每次没有匹配成功的时候，我们将 回退至上一个开始匹配位置 ，并重新匹配，这消耗了不少时间
KMP 的实现
而 KMP 算法则是在这个的基础上进行改进，使用前缀函数
next(i) 来提高效率
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int kmp_indexOf(string p, string s) {
vector<size_t> next = prefix_function(p);
size_t i = 0;
size_t j = 0;
while (j < p.size() && i < s.size()) {
if (j == 0 || s[i] == p[j]) {
i++;
j++;
} else
j = next[j];
}
if (j == p.size())
return i - p.size();
else
return -1;
}
|
这个算法和朴素算法的区别，在于对 和 的处理上，我们可以看到 kmp 算法中的
是只增不减的，而
我们通过前缀函数进行更新，这个更新的依据是，假设我们此时匹配到 ，发现 ，那么因为 告诉了我们在 ，上前后缀最多相等 的长度，又因为
，所以我们可以复用s[0,i-1]的后缀与前缀相等的部分，并把这一段当作新的前缀，那么我们就无需重新匹配这一部分了，因此我们仍可以从
开始匹配，对于 则为从 开始匹配
可以看到，这个算法是
的，在长度较大情况下效率远高于朴素算法