KMP算法原理与实现
概述
KMP是一种字符串匹配算法，其复杂度已经达到了该类算法的下界，即O(|T|+|P|)，其中T是文本串，P是模式串。下面介绍它的原理与实现。
MP算法（俗称）
下面我们介绍一种被称作MP算法的东西，这可以说是KMP算法的一个前身。
我们来尝试用P=”ABCD”来匹配T=”ABCABCABCD”，并观察它的过程。
第一步：P_0 \rightarrow T_0
ABCABCABCD |||X ABCD
第二步：P_0 \rightarrow T_1
ABCABCABCD X ABCD
第三步：P_0 \rightarrow T_2
ABCABCABCD X ABCD
第四步：P_0 \rightarrow T_3
ABCABCABCD |||X ABCD
……
第七步：P_0 \rightarrow T_6
ABCABCABCD
||||
ABCD
这便是朴素地匹配字符串的过程，我们发现要匹配完成一共尝试了7次。这个算法的复杂度是O(|T||P|)的。
下面我们想，如果在第一步P_3失配后能够直接转移到第四步的位置，因为我们会发现用T_1, T_2去匹配P是完全没有用的。我们需要知道，如果一个字符失配了，应该将P后移到哪里才能避免中间若干失配的情况。我们把这个信息表示为fail[i]失配数组，具体而言，失配数组表示如果当前位置失配了，应该将P的哪一位移到这里来。
我们会发现，失配需要移动的时候实际上是从当前位置之前的子串中找到一个最长的后缀，使得其与某一前缀相等。这个过程可以用自我匹配来完成。
inline void calfail() {
int i = 0, j = -1;
fail[0] = -1;
for(; pattern[i]; i++, j++) {
while(j >= 0 && pattern[j] != pattern[i]) {
j = fail[j];
}
fail[i + 1] = j + 1;
}
}
从当前位置开始往前的某个后缀是原串的某个前缀，那么后一位如果失配应该移至这个前缀的后一位。
举个例子，如果P=”ABABC”，fail数组应该看起来像这样
P= A B A B C fail=-1 0 0 1 2
当我们发现没有这样的后缀时，我们会到达P的头，得到fail[0]=-1这个值，这意味着我们需要将P整体后移了。现在我们匹配的思路也就明确了，即失配→用失配数组中的上一个位置对齐继续匹配，直到匹配完成。
下面就是一个匹配的实现。
inline int match() {
calfail();
int i = 0, j = 0, m = strlen(pattern);
for(; text[i]; i++, j++) {
while(j >= 0 && pattern[j] != text[i]) {
j = fail[j];
}
if(j >= m - 1) {
return i - m + 1;
}
}
}
现在的算法就是O(|P|+|T|)的了。
KMP算法
我们来观察一组MP的过程。现在T=”ABCABCABABC”，P=”ABABC”。
第一步：P_0 \rightarrow T_0
ABCABCABABC ||X ABABC
第二步：P_0 \rightarrow T_2
ABCABCABABC X ABABC
第三步：P_0 \rightarrow T_3
ABCABCABABC ||X ABABC
第四步：P_0 \rightarrow T_5
ABCABCABABC
X
ABABC
第四步：P_0 \rightarrow T_6
ABCABCABABC
|||||
ABABC
我们发现第二步、第四步的时候，我们老是在C这个位置失配，每次失配还要尝试2次，既然我们都知道了C和现在与fail指定的位置的A配不上，为什么不想办法把这段给跳过去呢？
接下来我们会更改fail的求法，使得中间重复的A被跳过去，实际上更改的方法也很简单。
inline void calfail() {
int i = 0, j = -1;
fail[0] = -1;
for(; pattern[i]; i++, j++) {
while(j >= 0 && pattern[j] != pattern[i]) {
j = fail[j];
}
fail[i + 1] = pattern[j + 1] == pattern[i + 1] ? fail[j + 1] : j + 1;
// 如果遇到了相同的字符，再往前跳一次
}
}
匹配的方法与上面MP的一样，只是fail有一点小区别而已。这个优化并没有影响整体复杂度，只是一个常数优化。
注意我们求出来的fail数组实际上比P串长一位，最后一位的值并没有用上。
代码
MP算法
本代码可以通过【P3375】【模板】KMP字符串匹配 – 洛谷，一题。
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
const int MAXN = 1000005;
int fail[MAXN];
char str1[MAXN], str2[MAXN];
inline void calfail() {
int i = 0, j = -1;
fail[0] = -1;
for(; str2[i]; i++, j++) {
while(j >= 0 && str2[j] != str2[i]) {
j = fail[j];
}
fail[i + 1] = j + 1;
}
}
inline void match() {
calfail();
int i = 0, j = 0, m = strlen(str2);
for(; str1[i]; i++, j++) {
while(j >= 0 && str2[j] != str1[i]) {
j = fail[j];
}
if(j >= m - 1) {
printf("%d\n", i - m + 2);
}
}
}
int main() {
scanf("%s%s", str1, str2);
match();
for(int i = 1; str2[i - 1]; i++) {
printf("%d ", fail[i]);
}
return 0;
}
KMP算法
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
const int MAXN = 1000005;
int fail[MAXN];
char str1[MAXN], str2[MAXN];
inline void calfail() {
int i = 0, j = -1;
fail[0] = -1;
for(; str2[i]; i++, j++) {
while(j >= 0 && str2[j] != str2[i]) {
j = fail[j];
}
fail[i + 1] = str2[j + 1] == str2[i + 1] ? fail[j + 1] : j + 1;
}
}
inline void match() {
calfail();
int i = 0, j = 0, m = strlen(str2);
for(; str1[i]; i++, j++) {
while(j >= 0 && str2[j] != str1[i]) {
j = fail[j];
}
if(j >= m - 1) {
printf("%d\n", i - m + 2);
}
}
}
int main() {
scanf("%s%s", str1, str2);
match();
for(int i = 0; str2[i]; i++) {
printf("%d ", fail[i]);
}
return 0;
}
参考资料
- 克努斯-莫里斯-普拉特算法 – 维基百科，自由的百科全书
- MPKMP算法详解 – 豆丁网
- 《算法竞赛入门经典 训练指南》，刘汝佳，陈锋著，清华大学出版社，9787302291077
