KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
虽然 KMP 是基础算法，但是却有着一定的难度，往往理解其算法思路后也难以用代码具体实现。在初学算法的道路上，算是一块难啃的骨头。于是，我决定花些时间好好研究一下这个神奇的算法。
我们提前约定：
1. S(STR) 代表“主串”;
2. P(PATTERN) 代表“子串”;
3. NextVal 为 Next 数组修正后的数组;
4. 本篇文章从程序的实际角度出发，下标统一从 0 开始。
同时，我将声明：本文为了便于理解，将 KMP 算法分成模块进行讲解。
一、KMP 算法基本理论
1.1 KMP 算法概述
相较于暴力破解的 BF 算法，KMP 算法的优点在于对主串的遍历不会回溯。
所以，当我们给予一个长度为 N 的主串时，使用 KMP 算法的时间复杂度即为 O(N)。
之所以能做到这一点，全靠 Next 数组记录了当主串字符与子串字符不匹配时（s[i] != p[j]），子串索引（j）可以直接跳转的位置（j = next[j]）。然后，继续比较即可，直至匹配成功或者匹配失败。
可以通过下面的动画理解⬇⬇：
1. 这个动画中 next[] = {-1, 0, 0, 1}
2. 这个动画中 next[] = {-1, 0, 0, 0, 1, 2, 3}
当然，这么讲肯定很晦涩难懂，特别对于第一次接触的朋友。所以，我建议先去看看视频动画演示的 KMP 算法，再来看这篇文章。
推荐视频讲解：KMP 算法工作原理——bilibili
1.2 代码实现 KMP 算法
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
| int KMP(char* s, char* p)
{
int pos = -1;
int s_len = strlen(s),
p_len = strlen(p);
int i = 0,
j = 0;
int* next = (int*)malloc(p_len * sizeof(int));
if (next)
{
getNext(p, next);
while (i < s_len)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
if (j >= p_len)
{
pos = i - j;
break;
}
}
free(next);
}
return pos;
}
|
二、Next 数组的基本理论
2.1 Next 数组生成概述
2.1.1 算法一
next 数组的生成主要有两种办法，我个人认为通过“最大共同元素长度”生成的方式没有通过“前一个字符的 next 值”生成的方式好。所以，我主要讲解第二种算法，第一种大家可以去看别的文章。
推荐文章：kmp算法 next[]数组的两种求法
下面着重介绍第二种算法（通过“前一个字符的 next 值”生成）：
首先可以确定的是 next[0] 一定是 -1，那么 k 的初始值一定是等于 next[0] 的（也就是 -1）。那么，j 的初始值也便可以为 1（因为 next[0] = -1 已经确定，只需要从 next[1] 开始确定 next 数组即可）。
使 k = next[j - 1]， 判断 p[j - 1] =?= p[k]：
- 如果
p[j - 1] == p[k]，那么就使 next[j] = next[j - 1] + 1 = k + 1; - 如果
p[j - 1] != p[k]，那么就使 k = next[next[j - 1]] = next[k]，然后再次判断 p[j - 1] =?= p[k]：- 如果
p[j - 1] == p[k]，那么就使 next[j] = next[next[j - 1]] + 1 = k + 1; - 如果
p[j - 1] != p[k]，那么就使 k = next[next[next[j - 1]]] = next[k]，然后再次判断 p[j - 1] =?= p[k]：- …
- 直到判断到
p[j - 1] == p[k] 或者 k == -1（此时 p[k] = p[-1] 已经不存在，无法比较）！
这样讲可能还是有些抽象，那么举个简单的例子：
- 我们使
char* p = {"ababaaa"}，（j = 0）然后使 next[0] = -1，
- （
j = 1）那么因为 k = next[j - 1] = next[0] = -1 ，因为 p[k] = p[-1] 不存在，所以 next[j] = next[1] = k + 1 = 0。
- （
j = 2）接着，k = next[j - 1] = next[1] = 0，判断 p[j - 1] = p[1] = 'b' 与 p[k] = p[0] = 'a' 不相同。所以，k = next[next[j - 1]] = next[k] = -1，因为 p[k] = p[-1] 不存在，所以 next[j] = next[2] = k + 1 = 0。
- （
j = 3）然后，k = next[j - 1] = next[2] = 0，判断 p[j - 1] = p[2] = 'a' 与 p[k] = p[0] = 'a' 相等。所以，next[j] = next[3] = k + 1 = 1。
- （
j = 4）接着，k = next[j - 1] = next[3] = 1，判断 p[j - 1] = p[3] = 'b' 与 p[k] = p[1] = 'b' 相等。所以，next[j] = next[4] = k + 1 = 2。
- （
j = 5）接着，k = next[j - 1] = next[4] = 2，判断 p[j - 1] = p[4] = 'a' 与 p[k] = p[2] = 'a' 相等。所以，next[j] = next[4] = k + 1 = 3。
- （
j = 6）接着，k = next[j - 1] = next[5] = 3，判断 p[j - 1] = p[5] = 'a' 与 p[k] = p[3] = 'b' 不相等。所以，k = next[next[j - 1]] = next[k] = next[3] = 1，继续判断 p[j - 1] = p[5] = 'a' 与 p[k] = p[1] = 'b' 不相等。所以，k = next[next[j - 1]] = next[k] = next[1] = 0，继续判断 p[j - 1] = p[5] = 'a' 与 p[k] = p[0] = 'a' 相等。所以，next[j] = next[4] = k + 1 = 1。
补充说明：next[1] 也必定等于 1，那为什么 j 不从 2 开始呢？
很简单，万一子串只有一个字符怎么办？
懂了吧！
2.1.2 算法二
略略略…
2.2 代码实现 Next 数组生成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| void getNext(char* p, int* next)
{
int k = -1,
j = 1,
len = strlen(p);
next[0] = -1;
while (j < len)
{
if (k == -1 || p[j - 1] == p[k])
{
k++;
next[j] = k;
j++;
}
else
{
k = next[k];
}
}
}
|
三、Next 数组修正的基本理论
3.1 Next 数组修正概述
3.1.1 为什么要修正？
在开始介绍修正算法之前还是得说一下为什么要进行 next 数组修正。
那么，让我们来看一组例子：
主串（S）：ababcababd
子串（P）：ababd
next 数组及 nextval 数组：
| 索引 | 0 | 1 | 2 | 3 | 4 |
|---|
| 子串（P） | a | b | a | b | d |
| next | -1 | 0 | 0 | 1 | 2 |
| nextval | -1 | 0 | -1 | 0 | 2 |
Ⅰ）使用原 next 的 kmp 算法：
| 主串（S） | 子串（P） | 关键判断 |
|---|
| ababcababd | ababd | === |
| ababcababd | ababd | === |
| ababcababd | ababd | === |
| ababcababd | ababd | === |
| ababcababd | ababd | =/= |
| ababcababd | ababd | next[4]=2 |
| ababcababd | ababd | =/= |
| ababcababd | ababd | next[2]=0 |
| ababcababd | ababd | =/= |
| ababcababd | ababd | === |
| … | … | === |
| ababcababd | ababd | === |
Ⅱ）使用 nextval 的 kmp 算法：
| 主串（S） | 子串（P） | 关键判断 |
|---|
| ababcababd | ababd | === |
| ababcababd | ababd | === |
| ababcababd | ababd | === |
| ababcababd | ababd | === |
| ababcababd | ababd | =/= |
| ababcababd | ababd | next[4]=2 |
| ababcababd | ababd | =/= |
| ababcababd | ababd | next[2] = -1 |
| ababcababd | ababd | === |
| … | … | === |
| ababcababd | ababd | === |
这么一来，使用 nextval 在处理类似的子串时就能减少一些不必要的判断，从而提高效率！
3.1.2 如何修正
这个算法并不难，可以用一段伪代码来表示：
1
2
3
4
5
6
7
8
9
10
11
12
13
| nextval[0] = next[0] = -1;
if p[i] =?= p[next[i]]
{
if 相同（===）
{
则 nextval[i] = next[next[i]];
}
else 不同（=/=）
{
则 nextval[i] = next[i];
}
}
|
3.2 代码实现 Next 数组修正
1
2
3
4
5
6
7
8
9
10
11
12
13
| void getNextval(char* p, int* next)
{
int i,
len = strlen(p);
for (i = 1; i < len; i++)
{
if (p[i] == p[next[i]])
next[i] = next[next[i]];
else
next[i] = next[i];
}
}
|
四、KMP 算法的完整代码（理解版）
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
| #include <stdio.h>
#include <malloc.h>
#include <string.h>
void getNext(char* p, int* next)
{
int k = -1,
j = 1,
len = strlen(p);
next[0] = -1;
while (j < len)
{
if (k == -1 || p[j - 1] == p[k])
{
k++;
next[j] = k;
j++;
}
else
{
k = next[k];
}
}
}
int KMP(char* s, char* p)
{
int pos = -1;
int s_len = strlen(s),
p_len = strlen(p);
int i = 0,
j = 0;
int* next = (int*)malloc(p_len * sizeof(int));
if (next)
{
getNext(p, next);
while (i < s_len)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
if (j >= p_len)
{
pos = i - j;
break;
}
}
free(next);
}
return pos;
}
int main(int argc, char* argv[])
{
char s[] = { "abcabcabcdefsdjklasjseayjllasdn" },
p[] = { "seayj" };
printf("pos=%d\n", KMP(s, p));
return 0;
}
#include <stdio.h>
#include <malloc.h>
#include <string.h>
void getNextval(char* p, int* next)
{
int i,
len = strlen(p);
for (i = 1; i < len; i++)
{
if (p[i] == p[next[i]])
next[i] = next[next[i]];
else
next[i] = next[i];
}
}
void getNext(char* p, int* next)
{
int k = -1,
j = 1,
len = strlen(p);
next[0] = -1;
while (j < len)
{
if (k == -1 || p[j - 1] == p[k])
{
k++;
next[j] = k;
j++;
}
else
{
k = next[k];
}
}
}
int KMP(char* s, char* p)
{
int pos = -1;
int s_len = strlen(s),
p_len = strlen(p);
int i = 0,
j = 0;
int* next = (int*)malloc(p_len * sizeof(int));
if (next)
{
getNext(p, next);
getNextval(p, next);
while (i < s_len)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
if (j >= p_len)
{
pos = i - j;
break;
}
}
free(next);
}
return pos;
}
int main(int argc, char* argv[])
{
char s[] = { "abcabcabcdefsdjklasjseayjllasdn" },
p[] = { "seayj" };
printf("pos=%d\n", KMP(s, p));
return 0;
}
|
五、KMP 算法代码（简洁版）
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| void getNextval(char* p, int* next)
{
int k = -1,
j = 1,
len = strlen(p);
next[0] = -1;
while (j < len)
{
if (k == -1 || p[j - 1] == p[k])
{
k++;
if (p[j] == p[k])
next[j] = next[k];
else
next[j] = k;
j++;
}
else
{
k = next[k];
}
}
}
int KMP(char* s, char* p)
{
int pos = -1;
int s_len = strlen(s),
p_len = strlen(p);
int i = 0,
j = 0;
int* next = (int*)malloc(p_len * sizeof(int));
if (next)
{
getNextval(p, next);
while (i < s_len)
{
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j = next[j];
}
if (j >= p_len)
{
pos = i - j;
break;
}
}
free(next);
}
return pos;
}
|
六、补充
2023年07月09日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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| namespace KMP_STD
{
internal class KMP
{
private const int MSG_KMP_MATCH_EXCEPTION = -1;
public const bool FLAG_OPTIMIZE_NEXT = true;
public const bool FLAG_NORMAL_NET = false;
public int[]? Next = null;
public bool GetNext(string P, bool WhetherToOptimize = FLAG_NORMAL_NET)
{
Next = new int[P.Length];
Next[0] = -1;
Next[1] = 0;
int j = 2, k = 0;
try
{
while (j < P.Length)
{
if (k == -1 || P[j - 1] == P[k])
{
if (FLAG_OPTIMIZE_NEXT == WhetherToOptimize)
{
++k;
if (P[j] == P[k])
Next[j] = Next[k];
else
Next[j] = k;
j++;
}
else
{
Next[j] = ++k;
j++;
}
}
else
{
k = Next[k];
}
}
}
catch (Exception e)
{
Console.WriteLine(e.ToString());
return false;
}
return true;
}
public int Match(string P, string S)
{
int PIndex = 0,
SIndex = 0,
FirstPos = -1;
try
{
while (PIndex < P.Length)
{
if (SIndex == -1 || P[PIndex] == S[SIndex])
{
PIndex++;
SIndex++;
}
else
{
SIndex = Next![SIndex];
}
if (SIndex == S.Length)
{
FirstPos = PIndex - S.Length;
break;
}
}
}
catch (Exception e)
{
Console.WriteLine(e.ToString());
return MSG_KMP_MATCH_EXCEPTION;
}
return FirstPos;
}
}
}
|
七、最新算法模板
该算法模板来自于 AcWing 的总结，相对于闫总的代码模板，这里改为下标统一从 0 开始。
相关代码同时存储在 Github 上。
具体地算法讲解可以看 AcWing 的这篇文章：深入浅出 next 数组。
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
| #include <iostream>
#include <vector>
#include <string>
static std::vector<int> computePrefixFunction(const std::string& pattern) {
int m = pattern.length();
std::vector<int> lps(m, 0);
int j = 0;
for (int i = 1; i < m; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = lps[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
lps[i] = j;
}
return lps;
}
static void KMP(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
std::vector<int> lps = computePrefixFunction(pattern);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = lps[j - 1];
}
if (text[i] == pattern[j]) {
++j;
}
if (j == m) {
std::cout << "Pattern found at index " << i - m + 1 << std::endl;
j = lps[j - 1];
}
}
}
|
微信
支付宝
