KMP 算法中的 next 数组推导(图解 + 代码实现)
KMP 算法中的 next 数组推导(图解 + 代码实现)
KMP算法是一种高效的字符串匹配算法，其核心是通过预处理模式串来避免不必要的字符比较。本文将详细讲解KMP算法中next数组的推导过程，通过图文结合的方式帮助读者深入理解这一经典算法。
KMP 算法中对 next 数组的理解
next 数组的意义
next数组在KMP算法中扮演着关键角色。具体来说，next[j]表示当位置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