KMP 算法中的 next 数组推导(图解 + 代码实现)
KMP 算法中的 next 数组推导(图解 + 代码实现)
KMP 算法中对 next 数组的理解
next 数组的意义
next[j] = k 表示当位置 j 的字符串与主串不匹配时，下一个需要和主串比较的字串位置在 next[j] 处。具体来说，k 前面的浅蓝色区域和 j 前面的浅蓝色区域相同。
若当前位置 j 与主串某一个字符不匹配，则下一次比较的是 K 与主串的当前位置，这个 K 也就是 next[j]。由于两个浅蓝色区域相同，因此 K 前面的区域肯定与主串相同，不需比较。
由上图可知，K 前面的区域不需比较。
next 数组的推导
先将求 next 数组的代码放在最前面，然后结合图片进行逐步分析：
void getNext(const string& s, int next[]) {
int len = s.size();
int j = 0; // 表示当前要求的 next[i]
next[0] = -1;
int k = -1; // 记录上一个 next
while (j < len - 1) {
if (k == -1 || s[j] == s[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
}
从 next 数组所表达的意义可知，我们要求 next[j]，首先要找到一个 K，这个 K 前面的浅蓝色区域和 j 前面的浅蓝色区域相同。
next[0] 和 next[1]
根据规定 next[0] = -1；接下来求其他的 next[j]；
对于 next[1] 可得其必然为 next[1] = 0；
如下图：当第二个元素不匹配时，j 将退回到 0 处进行比较，因此 next[1] 一定为 0；
因此代码中有：
int i = 0; // 表示当前要求的 next[i]
next[0] = -1;
int k = -1; // 记录上一个 next
if (k == -1) {
next[++j] = ++k;
}
- 规定 next[0] = -1；
- 当 k == -1 时，即 j==0 时；根据上面的推导 next[1] 一定为 0；
- next[++j]=++k，执行后即为 next[1]=0；以容易理解的方式写作：
next[j+1]=k+1;
k = k + 1;
j++;
接下来是一般情况的推导，此处使用递推法进行推导，即已知 next[j] 求 next[j + 1]；
next[j] = k 则有下图：
由于 next[j] = k，可知浅蓝色部分相同；接下来分两种情况讨论；
s[K] == s[j]
这种情况时，可以得到下图；
由图可知：对于 j + 1，能够找到一个 K + 1 使得有浅蓝色区域相同，那么当 j + 1 不匹配时，下一次将比较 K + 1 和主串；因此 next[j + 1] = K + 1 = next[j] + 1；
if (s[j] == s[k]) {
next[++j] = ++k;
}
- 根据分析，若 s[j]==s[k]，那么 next[j+1]=k+1；
- next[++i] = ++k 若写成更容易理解的方式为：下面的写法就和分析一致了；
next[j+1]=k+1;
k = k + 1;
j++;
s[K] != s[j]
这种情况就变的复杂，这也是整个 KMP 算法中最难理解的部分；
从本节的开头可以知道，求 next[j + 1] 最关键的一点在于求 j + 1 之前有多长的后缀和前缀匹配，即找出多大的浅蓝色区域匹配；我们现在面对的图如下：
我们的目的是找到一个 K1 使得出现下列情况：找到 K1 使得浅蓝色部分相同；
要想浅蓝色部分相同，分为两个部分，使得 1 和 2 相同，使得 K1 和 j 相同；
想要让 1 和 2 相同是难以比较的，但是可以转化为另一个问题，如下图：
想要找出 1 和 3 相同的区域，等价与找到 1 和 2 相同的区域；为什么呢？因为 next[j] = K，因此 j 前面与 K 前面相同如下图：
这个等价关系非常重要，是这部分推导的关键；将其单独抽离出来如下图：
那么如何得到 K1 使得 1 和 2 相同呢？回到文首 next[j] 所表示的意义，** next[j] = k ；则有 k 前面的浅蓝色区域和 j 前面的浅蓝色区域相同**而 next[K] 是在 j 前面的是已知的，因此可得 K1 = next[K]，此时得到的 K1 即可满足 1 和 3 相同；
到此就解决了 1 和 3 相等的问题，直接比较 K1 和 j 若两者相同，则可得到下图；
那么 next[j + 1] = K1 + 1 = next[K] + 1 = next[next[j]] + 1；
那么若 s[j] != s[K1] 呢？那么就又演化为如下问题：
这个图和本小节开始的图相同，那么按照此方法解决即可；
可得结果：
next[j + 1] = next[K1] + 1 = next[next[K]] + 1 = next[next[next[j]]] + 1
若下一次 K2 依然和 j 不相等，那么又接着递归即可；一直到 Kn = 1，若此时 s[j] != s[Kn]，即当前元素和第一个元素不相同，则证明在 j + 1 前面没有相同的前缀和后缀，那么 next[j + 1] = 0。
因此有代码：
if (k == -1 || s[j] == s[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
- else 的部分就表示 s[i]!=s[k]；
- 即不断的递归 k=next[k]
代码实现
通过以上分析得到的获取 next 数组的代码如下：
void getNext(const string& s, int next[]) {
int len = s.size();
int j = 0; // 表示当前要求的 next[i]
next[0] = -1;
int k = -1; // 记录上一个 next
while (j < len - 1) {
if (k == -1 || s[j] == s[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
}
那么接下来的 KMP 算法代码就比较容易了：
int KMP(const string &s, const string &p, int next[])
{
int i = 0, j = 0;
int slen = s.size();
int plen = p.size();
while (i < slen && j < plen)
{
// 对比第一个不匹配时，直接都 ++
if (j == -1 || s[i] == p[j])
{
i++, j++;
}
else
{
j = next[j];
}
}
return j == plen ? i - j : -1;
}
测试代码如下：
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void getNext(const string &s, int next[])
{
int len = s.size();
next[0] = -1;
int i = 0;
int k = -1;
while (i < len - 1)
{
if (k == -1 || s[i] == s[k])
{
next[++i] = ++k;
}
else
{
k = next[k];
}
}
}
int KMP(const string &s, const string &p, int next[])
{
int i = 0, j = 0;
int slen = s.size();
int plen = p.size();
while (i < slen && j < plen)
{
if (j == -1 || s[i] == p[j])
{
i++, j++;
}
else
{
j = next[j];
}
}
return j == plen ? i - j : -1;
}
int strStr(string haystack, string needle)
{
int next[10001];
getNext(needle, next);
return KMP(haystack, needle, next);
}
int main () {
string haystack = "abcleetcode";
string needle = "leetc";
cout << strStr(haystack, needle) << endl;;
}
输出结果：
3