警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」KMP

简介

KMP是一种在线性时间执行单模式串字符串匹配(以及其他一些问题)的算法。

BF算法

所谓的「BF算法」,也就是brute-force算法,时间复杂度是\(O(nm)\)的。也就是暴力匹配。

这显然是不行的,于是我们考虑优化。

优化

显然,并不是所有的匹配都是必要的。有一些匹配是注定不会成功的。

如下面的例子:

1
2
3
baaababaabbaabbbaabx
aababaabx
^

当已经进行到这一步时,显然如果只往右边移动一位

1
2
3
baaababaabbaabbbaabx
aababaabx
^

那么肯定是不能匹配上的。

注意到

1
2
3
4
baaababaabbaabbbaabx
aababaabx
--- ---
^

中用-标记出的两段是相同的且第二段的右端点正好是最后一个匹配到的字符。那么肯定只有把左端点移到第二段的左端点才会对答案有贡献了。所以失配后可以直接跳到

1
2
3
baaababaabbaabbbaabx
aababaabx
---

这可就省了一大截时间了:smile:。

怎么在程序里实现呢?

失配函数

失配函数,即「next数组」或「fail数组」。

这里统一使用「fail数组」。

x = fail[i],则S[0...x]和以i为右端点的等长后缀相等且x为最大值。例如

1
2
string: a a b a b a a b
fail : 0 1 0 1 0 1 2 3

我们暂时不考虑fail的求法。

这里的S[0...x]就是上面例子

1
2
3
4
baaababaabbaabbbaabx
aababaabx
--- ---
^

中的第一段,后缀就是例子中的第二段。

考虑到连续跳跃的可能性,代码实现如下:

1
2
3
while (match >= 0 && pattern[match + 1] != src[i]) {
match = fail[match];
}

其中i为源串匹配到的下标,match为模式串匹配到的下标。

加上匹配部分,我们可以得到以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void kmp() {
getfail();
int match = -1;
for (int i = 0; i < n; i++) {
while (match >= 0 && pattern[match + 1] != src[i]) {
match = fail[match];
}
if (pattern[match + 1] == src[i]) {
match++;
if (match == m-1) {
printf("%d\n", i - m + 2);
}
}
}
}

失配函数的求法

fail数组其实求起来很像。相当于是自己匹配自己。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
void getfail() {
fail[0] = -1;
int match = -1;
for (int i = 1; i < m; i++) {
while (match >= 0 && pattern[match + 1] != pattern[i]) {
match = fail[match];
}
if (pattern[match + 1] == pattern[i]) {
match++;
}
fail[i] = match;
}
}

代码

用于Accepted洛谷 P3375 - 【模板】KMP字符串匹配的代码如下:

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
#include <bits/stdc++.h>
using namespace std;

char src[1000006], pattern[1000006];
int fail[1000006];
int n, m;

void getfail() {
fail[0] = -1;
int match = -1;
for (int i = 1; i < m; i++) {
while (match >= 0 && pattern[match + 1] != pattern[i]) {
match = fail[match];
}
if (pattern[match + 1] == pattern[i]) {
match++;
}
fail[i] = match;
}
}

void kmp() {
getfail();
int match = -1;
for (int i = 0; i < n; i++) {
while (match >= 0 && pattern[match + 1] != src[i]) {
match = fail[match];
}
if (pattern[match + 1] == src[i]) {
match++;
if (match == m-1) {
printf("%d\n", i - m + 1 + 1);
}
}
}
}

int main() {
scanf("%s%s", src, pattern);
n = strlen(src);
m = strlen(pattern);
kmp();
for (int i = 0; i < m; i++) {
printf("%d ", fail[i] + 1);
}
return 0;
}