本文旨在讲解如何实现KMP三个核心思想 测试连接 : https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
KMP是什么
KMP(Knuth-Morris-Pratt)是一种高效的字符串查找算法, 其核心思想为使用部分匹配信息来避免重复比较，提升查找效率
三个核心思想
先看KMP代码:(测试连接为: https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
vector<int> next;
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
int x = 0, y = 0; // haystack, needle的下标
vector<int> next(m);
// O(m)
build(next, needle, m);
// O(n)
while (x < n && y < m) {
if (haystack[x] == needle[y]) {
x++;
y++;
} else if (y == 0) {
x++;
} else {
y = next[y];
}
}
return y == m ? x - y : -1; // 开头是x - y下标
}
// next数组如何快速生成
void build(vector<int>& next, string& needle, int& m) {
if (m == 1) {
next[0] = -1;
return;
}
next[0] = -1;
next[1] = 0;
int i = 2, cn = 0;
// i(m) i - cn(m)
// 上 上
// 不变 上
// 上 上
while (i < m) {
if (needle[i - 1] == needle[cn]) { // 从needle中的下标为2 - 1开始, 开始为neeedle[1] == needle[0]相等的情况下
// 后面为和上一个值相等的情况
next[i++] = ++cn; // 长度最多比之前多一个, 在与之前最大位置的值相等的情况下
} else if (cn > 0) { // cn > 0 : 当前位置还能往前蹦
cn = next[cn];
} else {
next[i++] = 0; // 跳到头都没出来
}
}
}
};
我将根据这个代码描述其核心思想
核心思想1 : next下标赋值
next数组的生成是KMP算法的核心部分。它记录了模式串中每个位置的最长相等前后缀长度。通过这个数组，KMP算法可以在匹配失败时快速跳过不必要的比较，从而提高效率, 因此next数组不同下标中存放的值是有讲究的:
- next[i] = x: 和needle[i]一一匹配, x则是needle[i]前面字符串前后缀匹配长度且前后缀不能为前面全部字符串
- next[0] = -1 : next中第一个字符不存在前后缀, 因此存放一个负值来表示
- next[1] = 0 : 前后缀不能为全部字符串, 因此为0
- 接下来同理
核心思想2 : KMP主体逻辑如何使用next加速匹配
1
2
3
4
5
6
7
8
9
10
while (x < n && y < m) {
if (haystack[x] == needle[y]) {
x++;
y++;
} else if (y == 0) {
x++;
} else {
y = next[y];
}
}
假设有一个子字符串aabaaf, 我们生成aabaaf的next数组:
- next[0] = -1
- next[1] = 0
- next[2] = 1
- next[3] = 0
- next[4] = 1
- next[5] = 2
我们从中不难发现:
当y = 4时, needle[4]之前的字符串为:aaba, needle[next[4] - 1]和needle[3]一样, 此时我们可以将比较needle[4]和haystack[x]进行比较改为needle[next[4]] (needle[1])与haystack[x]进行比较, 这样就可以避免对, needle[0]进行比较, 从而提高速度
核心思想3: next数组生成中使用cn加速
1
2
3
4
5
6
7
8
9
10
while (i < m) {
if (needle[i - 1] == needle[cn]) { // 从needle中的下标为2 - 1开始, 开始为neeedle[1] == needle[0]相等的情况下
// 后面为和上一个值相等的情况
next[i++] = ++cn; // 长度最多比之前多一个, 在与之前最大位置的值相等的情况下
} else if (cn > 0) { // cn > 0 : 当前位置还能往前蹦
cn = next[cn];
} else {
next[i++] = 0; // 跳到头都没出来
}
}
为什么可以通过cn进行加速生成next数组:
next[0] = -1, next[1] = 0已经被初始化了, 不算入其中
当其needle[i - 1]和needle[cn]相等时, next[i]存入值比之前 + 1, 因为相等时前后缀可以同时相比之前 + 1, 当其不相等时, cn如果大于0, 那么其可能存在与当前后缀相匹配的前缀就可以将后缀替换到前缀, 实现next加速生成
FAQ
为什么不用next[0] = 0, next[1] = 1初始化数组
next[0] = 0, next[1] = 1是标准版的KMP, 而next[0] = -1, next[1] = 0是failure function版本, 能够更好的处理next索引关系, 且可以使用cn加速构建next数组, 相比于标准版更优
