KMP算法

kmp算法原理和实现,转自:从头到尾彻底理解KMP(2014年8月22日版)

暴力算法

假设现在我们面临这样一个问题:有一个文本串S,和一个模式串P,现在要查找P在S中的位置,怎么查找?

如果用暴力算法的思路,并假设现在文本串S匹配到$i$,模式串P匹配到$j$位置,则有:

  • 如果当前字符串串匹配成功,即$S[i]==p[j]$,则$i++,j++$,继续匹配下一个字符;
  • 如果失败,即$S[i] != P[j]$,则令i=i-(j-1),j=0,相等于每次匹配失败时,$i$回溯,$j$被重置为0。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
using namespace std;

int strMatch(string & S, string & P) {
if (S.empty() || P.empty())
return -1;
int i = 0, j = 0;
while (j < P.size() && i < S.size()) {
if (S[i] == P[j]) {
++i, ++j;
}
else {
i = i - (j - 1);
j = 0;
}
}
return i - j;
}

int main() {
string S = "abcdefgad", P = "defga";
cout << strMatch(S, P) << endl;
}

还有变形,求模式串P是否在模式串S中存在,可以通过动态规划实现:

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
#include<vector>
#include<iostream>
#include<string>
using namespace std;

int strMatch(string & S, string & P) {
if (S.empty() || P.empty())
return -1;
int lenS = S.size(), lenP = P.size();
vector<vector<int>> dp(lenS+1, vector<int>(lenP+1, 0));
dp[0][0] = 0;
for (int i = 1; i <= lenS; ++i) {
dp[i][0] = 0;
}
for (int j = 1; j <= lenP; ++j) {
dp[0][j] = 0;
}
for (int i = 1; i <= lenS; ++i) {
for (int j = 1; j <= lenP; ++j) {
if (S[i - 1] == P[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[lenS][lenP];
}

int main() {
string S = "abcdefgad", P = "defga";
cout << strMatch(S, P) << endl;
}

以上两种实现的时间复杂度都是$o(n)$。

举个例子,如果给定文本串S“BBC ABCDAB ABCDABCDABDE”,和模式串P“ABCDABD”,现在要拿模式串P去跟文本串S匹配,整个过程如下所示:

  1. S[0]为B,P[0]为A,不匹配,执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,S[1]跟P[0]匹配,相当于模式串要往右移动一位(i=1,j=0)

    img

  2. S[1]跟P[0]还是不匹配,继续执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,S[2]跟P[0]匹配(i=2,j=0),从而模式串不断的向右移动一位(不断的执行“令i = i - (j - 1),j = 0”,i从2变到4,j一直为0)
    img

  3. 直到S[4]跟P[0]匹配成功(i=4,j=0),此时按照上面的暴力匹配算法的思路,转而执行第①条指令:“如果当前字符匹配成功(即S[i] == P[j]),则i++,j++”,可得S[i]为S[5],P[j]为P[1],即接下来S[5]跟P[1]匹配(i=5,j=1)

    img

  4. S[5]跟P[1]匹配成功,继续执行第①条指令:“如果当前字符匹配成功(即S[i] == P[j]),则i++,j++”,得到S[6]跟P[2]匹配(i=6,j=2),如此进行下去

    img

  5. 直到S[10]为空格字符,P[6]为字符D(i=10,j=6),因为不匹配,重新执行第②条指令:“如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0”,相当于S[5]跟P[0]匹配(i=5,j=0)

    img

  6. 至此,我们可以看到,如果按照暴力匹配算法的思路,尽管之前文本串和模式串已经分别匹配到了S[9]、P[5],但因为S[10]跟P[6]不匹配,所以文本串回溯到S[5],模式串回溯到P[0],从而让S[5]跟P[0]匹配。

    img

而S[5]肯定跟P[0]失配。为什么呢?因为在之前第4步匹配中,我们已经得知S[5] = P[1] = B,而P[0] = A,即P[1] != P[0],故S[5]必定不等于P[0],所以回溯过去必然会导致失配。那有没有一种算法,让i 不往回退,只需要移动j 即可呢?

答案是肯定的。这种算法就是本文的主旨KMP算法,它利用之前已经部分匹配这个有效信息,保持i 不回溯,通过修改j 的位置,让模式串尽量地移动到有效的位置。

KMP算法

KMP主要分为三个步骤:

  • 构造前缀表,即prefix table
  • 前缀表后移,并将第一个元素置为-1
  • KMP查找主体

对于前缀表的的构造:

最终需要的结果:

实现的具体思路:

通过观察发现上面的表格,ABABCA的最长公共前后缀的长度为1,最左边的字母和最右边的字母相同。要想公共前后缀长度变长,变成2。唯一的做法在字符串末尾添加一个跟第二字母相同的字母。可以发现前后字符串的最长公共前后缀是有关系的。

如果pattern[i] == pattern[len],表示最长公共前后缀的长度需要加1。

前缀表(prefix table)代码实现:

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
vector<int> prefix_table(string & pattern) {
int n = pattern.size();
vector<int> prefix(n);
prefix[0] = 0;
int len = 0, i = 1;
while(i < n) {
if (pattern[len] == pattern[i]) {
++len;
prefix[i] = len;
++i;
}
else {
if (len > 0) {
len = prefix[len - 1];
}
else {
prefix[i] = len; //len=0
++i;
}
}
}

return prefix;
}

void move_prefix_table(vector<int> & table) {
for (int i = table.size() - 1; i > 0; --i) {
table[i] = table[i-1];
}
table[0] = -1;
}

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
void kmp_search(string & S, string & P) {
vector<int> prefix = prefix_table(P);
move_prefix_table(prefix);

//S[i] lenS
//P[j] lenP
int i = 0, j = 0;
int lenS = S.size(), lenP = P.size();
while (i < lenS) {
if (j == lenP - 1 && S[i] == P[j]) {
cout << "Found pattern at " << i - j << endl;
j = prefix[j];
}
if (S[i] == P[j]) {
++i, ++j;
}
else {
j = prefix[j];
if (j == -1) {
++i, ++j;
}
}
}
}

完整的代码:

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
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> prefix_table(string & pattern) {
int n = pattern.size();
vector<int> prefix(n);
prefix[0] = 0;
int len = 0, i = 1;
while(i < n) {
if (pattern[len] == pattern[i]) {
++len;
prefix[i] = len;
++i;
}
else {
if (len > 0) {
len = prefix[len - 1];
}
else {
prefix[i] = len; //len=0
++i;
}
}
}

return prefix;
}

void move_prefix_table(vector<int> & table) {
for (int i = table.size() - 1; i > 0; --i) {
table[i] = table[i-1];
}
table[0] = -1;
}

void kmp_search(string & S, string & P) {
vector<int> prefix = prefix_table(P);
move_prefix_table(prefix);

//S[i] lenS
//P[j] lenP
int i = 0, j = 0;
int lenS = S.size(), lenP = P.size();
while (i < lenS) {
if (j == lenP - 1 && S[i] == P[j]) {
cout << "Found pattern at " << i - j << endl;
j = prefix[j];
}
if (S[i] == P[j]) {
++i, ++j;
}
else {
j = prefix[j];
if (j == -1) {
++i, ++j;
}
}
}
}

int main() {
string S = "ABABABABCABAABABABCABAA", P = "ABABCABAA";
vector<int> table = prefix_table(P);
move_prefix_table(table);
for (int i = 0; i < table.size(); ++i)
cout << table[i] << endl;
kmp_search(S, P);
return 0;
}

参考:

[1] https://blog.csdn.net/v_july_v/article/details/7041827

[2] http://blog.rexking6.top/2017/08/07/KMP%E7%AE%97%E6%B3%95/

[3] https://www.bilibili.com/video/BV1hW411a7ys

zxp wechat
欢迎关注微信公众号!