因为上周末 MFE 群里有位成员提到了这个算法，所以那天晚上就稍微认识了一下这个算法，感觉 KMP 对于匹配字符串上的做法还是好神奇的，值得水篇文章整理一下。
很久没有更文了w 最近真的是非常非常非常忙qwq，刚刚送走了第二次阶段考就迎来了 NOIP 的初赛，然后接下来的一整个月都要在忙碌的准备中度过，11 月回来又是期中考qwq 所以你们会发现我的解题报告停更了半个月，这篇文章权当是补偿吧（
KMP 算法
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
以上摘自百科，这段话已经详尽地阐明了什么是 KMP 算法、它的应用场景和高效性的核心原因。下面就不再多做介绍了w。
原始的字符串匹配方法
首先回忆一下，如果我们要匹配两个字符串，一般是怎么做的？我想大部分的人应该会想到这样的答案：
- 用两个下标指针 i, j 分别指向我们要匹配的目标字符串 (target) 和给我们的模式串 (pattern)。
- 从 i = 0 作为起点开始，如果 target[i] == pattern[j]，就一步一步向右移动 i, j 指针。
- 当 target[i] != pattern[j] 的时候，就让 i 的起点右移一位，让 j = 0.
- 重新开始尝试匹配，直到匹配成功（返回 target 与 pattern 匹配的起始为止）或者 i = target.length 时仍然没有结果为止（此时 target 与 pattern 不匹配，返回 -1）。
当然，这样的方法确实是正确的说，但是我们还需要考虑这个效率 efficiency。很明显这个方法的时间复杂度是 O(n*m) 的~ 要是数据量很大的话就可能会超时哟（
那么有没有什么好一点的方法来优化我们匹配两个字符串的方式呢？
优化的思想
下文中，我们把目标串 target 记作 T, 模式串 pattern 记作 P. 首先，让我们考虑这样两个字符串：
target (T): ABCABCABDAB
pattern(P): ABCABD
我们用上面的方法匹配的时候，让 i = j = 0，然后当 T[i] == P[j] 的时候，我们不断让 i, j 右移，直到 i = j = 5 的时候，我们发现 T[i](C) != P[j](D) 了。
按照我们上面的思路，我们会把 i 和 j 回溯：
↓ i = 1
ABCABCABDAB
ABCABD
↑ j = 0
这时候第一个字符就不匹配了，所以 i 继续右移，直到 i = 3, j = 0 的时候往下匹配，最后 i = 8, j = 5 的时候匹配成功：
↓ i = 3
ABCABCABDAB
ABCABD
↑ j = 0
......
↓ i = 8
ABCABCABDAB
ABCABD
↑ j = 5
但是我们发现了一件有趣的事情，就是，如果这件事让我们人为来做的话，当 i, j 从 0 开始匹配到 5 失败的时候，我们不会让 i = 1, 2, … 这样一直试到匹配为止。 因为我们发现我们在 i = 5 的时候匹配失败，P[0] = A, 但是 i = 5 的前面只有 i = 3 的时候 T[i] = A，所以 i = 1, 2 的时候我们根本不需要去匹配。我们能这么想，是因为我们已经知道匹配过的 i = 0~5 的情况了——这也正是 KMP 算法的精髓所在，KMP 算法高效的原因之一正是由于它能够利用已经匹配到的有效信息。
所以呢，上面提到的三个人就想到了一个方案：i 指针可以不动呀，我们只要移动 j 指针就可以了。
↓ i = 5
ABCABCABDAB
ABCABD
↑ j = 5
这个时候让 i 不动，只移动 j：
↓ i = 5
ABCABCABDAB
ABCABD
↑ j = 2
哎，你会发现这样比一起移动 i 和 j 快多了，对吗？这就是 KMP 算法的思想：
利用已经部分匹配这个有效信息，保持 i 指针不回溯，通过修改 j 指针，让模式串尽量地移动到有效的位置。
KMP 算法的灵魂 —— j 指针移动的位置
但是有人会问，我们要怎么知道 j 指针移动到哪个地方才合适呢？因为 j 的下一个位置很关键，如果 j 的下一个位置太提前，那么这个想法无异于没有优化；如果太靠后，那么两个字符串就无法匹配了。所以 j 指针的下一个位置是很重要的。KMP 算法中，用一个叫 next 数组 的东西来记录 j 指针的下一个位置。
next 数组也是 KMP 的难点所在。如果你觉得 next 数组的求解很难理解，这里有几篇文章可以辅助你理解；下面我也会理一下从这几篇文章里整理出来的比较容易理解的东西：
http://www.cnblogs.com/yjiyjige/p/3263858.html http://blog.csdn.net/henuyx/article/details/44653799
我们用 k 表示当 T[i] 与 P[j] 不匹配的时候，j 要移动的下一个位置，则 next[j] = k. 现在你可以猜到，next[j] 存储的是：当 T[i] 与 P[j] 匹配失败时，j 将要移动的下一个位置。
我们还是举上面那个例子吧：
ABCABD
↑ j = 5，匹配失败
ABCABD
↑ j = 2，把 j 移动到这个位置
有没有发现什么？没错， P[0~1] 和 P[3~4] 是重合的！
再比如说：
↓ i = 7
ABCDABCDNAIVE
ABCDABCB
↑ j = 7
这个时候又匹配失败了。虽然我们作为人类，很容易看出这两个字符串无论怎么移动都不能匹配。不过我们这个时候还是要假装尝试一下，我们会这样移动 j 指针：
移动前：
↓ i = 7
ABCDABCDNAIVE
ABCDABCB
↑ j = 7
移动后：
↓ i = 7
ABCDABCDNAIVE
ABCDABCB
↑ j = 3
哎，是不是还是刚才的那个规律呢，模式串的 P[0~2] 和 P[4~6] 是重合的，而恰恰又是 j 移动的位置 3 把它们隔开了。
现在我们可以总结出这样的性质了：当 T[i] 与 P[j] 匹配失败的时候，j 移动到下一个位置 k，k 即为使得 P[0, k-1] = P[j-k, j-1] (或者说 P[k+1, j-1]) 的那个值。
引用一下一篇文章的证明：
当T[i] != P[j]时 有T[i-j ~ i-1] == P[0 ~ j-1] 由P[0 ~ k-1] == P[j-k ~ j-1] 必然：T[i-k ~ i-1] == P[0 ~ k-1]
进一步我们还可以发现，这个 k 的位置完全取决于模式串 P 自身的性质，与目标串 T 无关。所以我们就可以预处理计算出对于每一个 j 的 k 值了。就如我们刚才所说的我们把 k 存储在 next 数组当中，那么接下来我们就来计算 next 数组。
next 数组的计算
先温习一下 next 数组的含义和作用：
next[j] 存储的是：当 T[i] 与 P[j] 匹配失败时，j 将要移动的下一个位置。
接下来我们分类讨论一下：
- 当 j = 0 的时候，显然 j 已经不能再往前移动了，我们这个时候应该保持 j 不动，然后向右移动 i 指针继续匹配。所以我们让 next[0] = -1，告诉 KMP 主算法已经不能再移动 j 指针了。
- 当 j = 1 的时候，显然 j 只能移动到 0，所以 next[1] = 0.
- 那么其他情况呢？如果 P[j] = P[k] 的话，那么 next[j+1] = next[j] + 1.
- 最后一种情况就是 P[j] != P[k]，那么我们就让 k = next[k], 重复这个步骤直到符合上面三个条件之一为止。
至于为什么这样做，这里主要介绍一下 3 和 4：
为什么 P[j] = P[k] 的时候，next[j+1] = next[j] + 1 呢？
考虑这样一个字符串：
index 0 1 2 3 4 5 6 7 8
str A B C D A B C D E
next -1 0 0 0 0 0 0 3 4
通过计算我们可以发现 next[7] = 3, 因为 3 的左边和右边都是 ABC，这个时候我们发现 P[7] = P[3] = D.
所以，我们发现，当 j = j+1 = 8 之后，next[8] = 4 = next[7] + 1. 这个规律也是可以证明的。这个证明同样是引用：
因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k） 这时候现有P[k] == P[j]，我们可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。 即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。
那 P[j] != P[k] 的时候呢？
如果没有赋值的时候，next[j] 默认是等于 0 的，否则 k 就是上一次计算的 k 值。 这样，当 P[j] != P[k] 的时候，我们就一直让 k = next[k]，直到 k 符合上面的条件之一为止。
鉴于……这个东西我也讲不清楚qwq 所以我找到了一篇总结的挺好的文章：https://www.zhihu.com/question/21474082。 虽然内容不长，但是我就不贴过来了。
那么，我们可以整理出计算 next 数组的整个过程了：
初始化 next[] = 0
next[0] ← -1
j ← 0, k ← -1, len ← (pattern 长度 - 1)
while j < len do
if k = -1 || pattern[j] = pattern[k] then
j ← j+1, k ← k+1
next[j] = k
else
k ← next[k]
下面是一个用 C++ 实现的方式：
void calcNextArr()
{
next[0] = -1;
int j = 0, k = -1, len = strlen(pattern) - 1;
while (j < len)
{
if (k == -1 || pattern[j] == pattern[k]) {
next[++j] = ++k;
// 如果要做时间复杂度优化，就加上下面的代码
if (pattern[j] == pattern[k]) {
next[j] = next[k];
}
} else {
k = next[k];
}
}
}
优化 next 数组的求解
注意到我们在实现上面的伪代码的时候多了两句：
if (pattern[j] == pattern[k]) {
next[j] = next[k];
}
为什么要加这一句呢？我们可以看出如果 P[j] = P[k] 的时候，让 next[j] = next[k]. 但是我们上文不是说到，如果 P[j] = P[k] 的时候，next[j+1] = next[j] + 1 嘛，为什么又回去了呐？考虑这样的一个模式串：
ABCABDNAIVE
ABCABCABDAB
↑ j = 5
如上，当我们在 j = 5 的地方匹配失败的时候，按照我们上面的算法，next[j] = 2，所以 j 会回溯到 2 的地方，指向 C. 但是我们发现就算 j 回溯到 j = 2 的时候，P[j] 仍然等于 C，依旧不能和目标串匹配啊。所以我们还是要把 j 继续回溯，那么这时候 next[j] = 0. 相信大家想到了，只要我们让 j = 5 的时候直接跳回 0，就可以省去多跳一步的步骤了，这就是这段代码的作用。
KMP 主算法
了解了 next[] 数组之后，你已经完全了解 KMP 不远了。 接下来是 KMP 算法的整个流程 ：
T ← 目标串，P ← 模式串
i ← 0, j ← 0
next[] ← calcNext(P) // 对模式串 P 计算其 next 数组的值
while i < T.length && j < P.length do
// 如果 j 已经指向模式串的起点了，就把 i 下移一位，j 置零；或者 T[i] 和 P[j] 匹配了，那么就把 i, j 一起下移一位
if j == -1 || T[i] == P[j] then
i ← i+1, j ← j+1
// 如果不匹配，那就让 j 回溯到 next[j] 位置
else
j ← next[j]
if j >= P.length // 此时匹配成功
return i-j // i-j 即为 T 与 P 匹配时 T 串开始的位置
else
return -1 // 否则返回不匹配，用 -1 表示
仍旧是一份 C++ 实现的模板：
int KMP()
{
int i = 0, j = 0;
int tlen = strlen(target), plen = strlen(pattern);
while (i < tlen && j < plen)
{
if (j == -1 || target[i] == pattern[j]) {
i++, j++;
} else {
j = next[j];
}
}
if (j == plen) {
return i - j;
} else {
return -1;
}
}
解决实际问题
HDU2087
地址在这里：http://acm.hdu.edu.cn/showproblem.php?pid=2087
分析题目我们可以发现这就是一道简单的裸题字符串匹配，我们当然可以直接上 KMP 啦。下面是这题的 AC 代码：
#include <cstdio>
#include <cstring>
const int MAXN = 1e3 + 10;
int n[MAXN];
char target[MAXN], pattern[MAXN];
void init()
{
memset(target, 0, sizeof target);
memset(pattern, 0, sizeof pattern);
memset(n, 0, sizeof n);
}
void calcNext()
{
n[0] = -1;
int i = 0, k = -1, len = strlen(pattern) - 1;
while (i < len)
{
if (k == -1 || pattern[i] == pattern[k]) {
n[++i] = ++k;
if (pattern[i] == pattern[k]) {
n[i] = n[k];
}
} else {
k = n[k];
}
}
}
int KMP()
{
int ans = 0, i = 0, j = 0;
int tlen = strlen(target), plen = strlen(pattern);
while (i < tlen)
{
if (j == -1 || target[i] == pattern[j]) {
i++, j++;
} else {
j = n[j];
}
if (j == plen) {
j = 0;
ans++;
}
}
return ans;
}
int main()
{
while (~scanf("%s", target))
{
if (target[0] == '#')
break;
scanf("%s", pattern);
calcNext();
int ans = KMP();
printf("%d\n", ans);
init();
}
return 0;
}
luogu 3375
这题也是个 KMP，可能有多个匹配，那么它要输出每个匹配的位置；以及这题的 next 数组不能优化，因为他还要输出= =我就是用了优化的 next 数组然后 WA 了好多次（ 总之写起来大概像下面这样：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1000050;
int next[MAXN], n[MAXN];
int len1, len2;
char target[MAXN], pattern[MAXN];
void calcNext()
{
int j = 0, k = -1;
next[0] = -1, n[0] = -1;
while (j < len2)
{
if (k == -1 || pattern[j] == pattern[k]) {
next[++j] = ++k;
n[j] = k;
if (pattern[j] == pattern[k]) {
n[j] = n[k];
}
} else {
k = next[k];
}
}
}
void kmp()
{
int i = 0, j = 0;
while (i < len1)
{
if (j == -1 || target[i] == pattern[j]) {
i++, j++;
} else {
j = n[j];
}
if (j == len2) {
printf("%d\n", i - j + 1);
j = n[j];
}
}
}
int main()
{
scanf("%s%s", target, pattern);
len1 = strlen(target);
len2 = strlen(pattern);
calcNext();
kmp();
for (int i = 1; i <= len2; i++)
{
printf("%d ", next[i]);
}
printf("\n");
return 0;
}
至此，我们对 KMP 的算法就有了一个比较完整的了解了。