一、KMP的背景
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现
因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
from –百度百科
二、KMP解决的问题
2.1 KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字（接下来称它为P），如果它在一个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常用手段）。
2.2、假设现在我们需要观察”hello”字符串与”213helldshello”是否匹配
采用传统的暴力法如下所示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int main(int argc, const char * argv[])
{
//观察"hello"字符串与"213helldshello"是否匹配
string dStr = "213helldshehello";
string keyStr = "hello";
for (decltype(dStr.size()) i = 0; i < (dStr.size() - keyStr.size()); ++i) {
for (auto j = i; j < (keyStr.size() + i); ++j) { //开始匹配字符
if (dStr.at(j) != keyStr.at(j)) { //如果不匹配,就终止当前循环
break;
}
if (j == (keyStr.size() + i - 1)){ //如果最后一个字符也匹配成功,就输出匹配成功
cout << "匹配成功" << endl;
return 0;
}
}
}
cerr << "匹配失败";
return -1;
}
|
2.3、核心问题所在
一旦匹配失败，将要重头匹配，导致复杂度升高（主要是逼格低，所以kmp的核心思想是“利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置”（别挣扎了，这句话光看是看不懂了，跳过往下看吧
三、KMP简单实现
3.1、getNext()
当此次匹配失败后,下一次不从下一个重新匹配,而是根据前面的匹配信息选择平移一段距离来匹配,具体平移多长的距离,由getNext()方法来决定.所以接下来我们要讨论到底要移动多长合适
观察如下匹配
1
2
| 213kittzshellokitty
kitty
|
我们可以发现到这里的时候,只有前4位匹配成功,根据之前所说的平移,那我们要决定平移多少合适这么一看,我们完全可以平移4位接着匹配.
所以是不是成功匹配多少，就移位多少呢？
很巧，不是的，瞧下面一个例子
这个时候我们同样发现前4个是匹配的,但是只有匹配一个位就合适了
所以核心问题是解决要移动几个位
3.2、公共前后缀&&getNext（）
我们观察匹配到的字符串,即如上面的kkkki,他匹配到kkkk时发现剩下的h不匹配,此时他的最大匹配串就是kkkk.然后我们观察他的首尾有最多几个一样的字符串.
比如
aba 首位的a和末尾的a相同 所以最大公共前后缀的就是1
asdasc 这种字符串找不到首位匹配的,所以最大公共前后缀为0.
asdas 首位的as 相同 所以最大公共前后缀就是2.
这种做法有什么意义呢,当我们发现字符串的长度是n的时候,如果他的公共前后缀长度为0,那么我们就平移他的长度n(n-0=n)
getNext返回值是（公共匹配长度-最大公共前后缀）
最大公共前后缀其实可以总结为next数组，思想一样，只是算法不同
3.3、浅显证明一下（不是很严谨，只是希望能够记住
我们要匹配
1
2
| kittittyhelloworld
kitty
|
开始匹配时,发现前4位是正好匹配的,他的公共匹配是kitt我们发现他的公共前后缀长度是0,所以这个时候我们平移4位.
现在假设我们这样的做法是错误的，其实移动三格就能匹配到（这是假设
1
2
| kittittyhelloworld
kitty
|
如果假设要成立，那么原字符串的第四位一定是k才能匹配到kitty
即公共匹配的4位是kitk,最大公共前后缀为1,所以就应该平移3位,刚好对应我们的假设
（不知道听懂了没，全跟着感觉走咯）
四、算法
4.1、实现getNext（）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int getNext(string maxStr){
int length = maxStr.size();//存放字符串的长度
string str1;
string str2;
int subLen = 0;
for (int i = 1 ; i < length; ++i) {//截取两段字符串
str1 = maxStr.substr(0,i);
str2 = maxStr.substr(length-i,length);
if(str2 == str1){//比较
subLen = i;
}
}
return length - subLen;//此地用的不是next数组，其实subLen可以用以计算next数组
}
|
4.2、主函数
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
| int main()
{
/*
目标字符串:HelloworldiamKittyihiahiahia
匹配字符串:Kitty
*/
string deStr("HelloworldiamKittyihiahiahia");
string keyStr("Kitty");
//1.先匹配,找到匹配到的公共最大匹配串,需要一个字符串maxStr来保存
string maxStr("");
int steps;
int length; //用于循环中计算当前长度
//2.开始匹配
for (int i = 0; i < (deStr.size() - keyStr.size());) {
length = 0;//每次重新搜索都把length置0
steps = 1;//每次平移一段距离都重新计算平移的距离
for (int j = i; j < (keyStr.size() + i); ++j) {
if (deStr.at(j) != keyStr.at(j-i)) {
if ( length > 1) {
maxStr = keyStr.substr(0,length);
//***************
steps = getNext(maxStr); //这里需要一个函数,来告诉我们每次需要跳过多少次
//***************
}
break; //如果当前循环不一致则结束循环
}
++length; //匹配成功字符串长度加1
if (length == keyStr.size()){
cout << "匹配成功" << endl;
cout<<"匹配成功第一次的第一个字符的下标为："<<i<<endl;
return 0;
}
}
i += steps;
}
cout << "匹配不成功";
return -1;
}
|