[ 生活需要仪式感 ]

0%

关于KMP算法的思考

KMP算法通过对自己模式串的计算,能够使得匹配过程中主串的指针不用回溯,从而优化匹配过程。

#原理
每次的匹配过程中出现[失配]时,主串的指针不用回溯,而是利用”部分匹配”的表将模式串向右滑动尽可能远的距离,然后继续与主串比较。

部分匹配表,我个人认为其实就是模式串首尾可能出现相同的字符,我们通过计算可以得知一些跳动的步数,并记录在表中。当匹配进行时,模式串尾部失配,那么,可以通过向右移动,模式串的首部向右推动到尾部,重新进行匹配,则大大提高了匹配的效率。

#优势
对比简单的匹配算法,通过一个神奇的j=next[j]代码,(先不表这个数组是怎么求出来的,部分匹配表的体现),KMP可以不用每次都让主串指针回溯,让匹配君得到buff,只要移动模式串,就能够调到下一个很有可能成功匹配的位置,能够大大减少一些重叠的过程。

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
/////////////////////////////////
# 第一次
i

i: 1234567890 //主串指针
S: ababcabcac //主串
T: abcac //模式串
j: 1234567890 //模式串指针

j

/////////////////////////////////

# 第二次
i

i: 1234567890 //主串指针
S: ababcabcac //主串
T: abcac //模式串
j: 1234567890 //模式串指针

j

>>>出现失配<<<
>>>前方高能<<<
/////////////////////////////////

# 第三次(高能的buff发挥作用)
i

i: 1234567890 //主串指针
S: ababcabcac //主串
T: abcac //模式串
j: 1234567890 //模式串指针

j
(通过j=next[j],能够“失配”知道下一步j跳到哪一步,如这里跳到6)
/////////////////////////////////

#next[]要点
通过一个递归算法,相同就先纪录回退点,然后继续递归算法。不行就回退。

#实现代码(c++)

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
//  main.cpp
// 字符串匹配测试
//
// Created by Copriwolf on 15/10/21.
// Copyright 2015年 Copriwolf. All rights reserved.
//

#include <iostream>
using namespace std;

int Welcome(string& S, string& T,int &choose);
int SimplePatternMatching(string S, string T,int pos);
class KMP{
public:
int next[];
int KMP_Matching(string S,string T,int pos);
int KMP_NextArray(string S,string T,int pos);
};


int main(int argc, const char * argv[]) {
int choose=0;
int pos=0;
string S,T;

Welcome(S,T,choose);
switch (choose) {
case 1:
cout<<"简单匹配算法成功运行"<<endl;
cout<<"模式串在主串中第"<<SimplePatternMatching(S, T, pos);
cout<<"个字符之后的位置!"<<endl;
cout<<"///////////////////////////////"<<endl;
break;
case 2:{
cout<<"KMP匹配算法成功运行"<<endl;
KMP kmp;
kmp.KMP_NextArray(S, T, pos);
cout<<"模式串在主串中第"<<kmp.KMP_Matching(S, T, pos);
cout<<"个字符之后的位置!"<<endl;
cout<<"///////////////////////////////"<<endl;
break;
}
case 0:
exit(0);
default:
cout<<"Your input a wrong number!Please try again!";
cout<<"///////////////////////////////"<<endl;
break;
}
return 0;
}

//欢迎界面
int Welcome(string& S, string& T,int& choose){
cout<<"Welcome:)"<<endl;
cout<<"Please input the Original text:"<<endl;
S="";
getline(cin,S);
cout<<"Please input the Pattern text:"<<endl;
T="";
getline(cin,T);
cout<<"please select your choose:"<<endl;
cout<<"[1]简单匹配算法;[2]KMP匹配算法;[0]退出"<<endl;
cin>>choose;
return choose;
}

//简单匹配实现
int SimplePatternMatching(string S,string T,int pos){
int i=pos;
int j=0;
while ((i<= int(S.length()))&&(j<= int(S.length()))) {
if (S[i] == T[j]) {++i; ++j;}
else{i=i-j+2;j=1;}
}
if (j >int(T.length())) return (i-int(T.length()));
else return 0;
}


//KMP匹配实现
int KMP::KMP_Matching(string S,string T,int pos){
int i=pos;
int j=0;
while ((i<= int(S.length()))&&(j<= int(S.length()))) {
if (S[i] == T[j] || j==0) {++i; ++j;}
else{
j= next[j];
}
}
if (j >int(T.length())) return (i-int(T.length()));
else return 0;
}

int KMP::KMP_NextArray(string S,string T,int pos){
int i=pos;
int j=1;
while ((i <= int(T.length()))&& (j <= int(T.length()))) {
if (j ==0 || int(T.length()) == int(S.length())) {
++i;
++j;
}
else{
j=next[j];
}
}
if (j >int(T.length())) {
return (i-int(T.length()));
}
else{

return 0;
}
}

#参考资料

  • 《数据结构(C语言版)》严蔚敏,吴伟民著
  • 《字符串匹配的KMP算法》阮一峰著,博文链接
  • 《从头到尾彻底理解KMP》July著,博文链接