算法---- KMP算法之我觉得自己说得很好懂
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n).
from --百度百科
---首先,我们需要更细致的了解这个算法是为了解决哪种问题.
Q:
using namespace std;
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;
}
小结:这种最基本的匹配思路是大家能想到的思路上最简单,最直接的方法.只不过我们可以发现他好麻烦呐,每次都要重头匹配.然后就有人琢磨优化,然后我们如今就能得到别人的研究成果--kmp.
简单介绍: kmp算法是一种平移算法(沃渍基取的名字).他把之前匹配的信息保留下来,当此次匹配失败后,下一次不从下一个重新匹配,而是根据前面的匹配信息选择平移一段距离来匹配,具体平移多长的距离,由getNext()方法来决定.所以接下来我们要讨论到底要移动多长合适
观察"hello"字符串与"213helldshello"是否匹配
213helldshello
hello
我们可以发现到这里的时候,只有前4位匹配成功,
根据之前所说的平移,那我们要决定平移多少合适
这么一看,我们完全可以平移4位接着匹配.
但是就会有人开始举反例,比如
ssssshesss --字符串
ssssh --匹配字符串
这个时候我们同样发现前4个是匹配的,
然后我们发现需要平移多少合适呢?
是不是平移1位就能匹配到啦.
这个就麻烦了,我们完全不知道什么时候移多点,什么时候移少点.这个时候需要引入一个概念
覆盖函数
我们观察匹配到的字符串,即如上面的ssssh,他匹配到ssss时发现剩下的h不匹配,此时他的最大匹配串就是ssss.然后我们观察他的首尾有最多几个一样的字符串.
比如
aba 首位的a和末尾的a相同 所以最大公共的就是1
asdasc 这种字符串找不到首位匹配的,所以为0.
asdas 首位的as 相同 所以最大公共的就是2.
这种做法有什么意义呢,当我们发现字符串的长度是n的时候,如果他的公共前后缀(就是前面首位相同的字符串)长度为0,那么我们就平移他的长度n.
比如 asdjsdjassda
asdjas
开始匹配时,发现前4位是正好匹配的,他的公共匹配是asdj
我们发现他的公共前后缀长度是0,
所以这个时候我们平移4位.
这个时候我们不管怎么去设计后面的数据,都不会发生漏掉匹配串的现象.
比如这两个字符串,如果我们匹配到了4个,而且平移3位就能使其匹配,
那么我们就必须要
asdjsdjassda
asdjas
我们发现如果要匹配成功,公共匹配的4个最后一位一定要改成a
即
asdasdjassda
asdjas
这个时候我们发现他的最大公共前后缀为1,所以就应该平移3位,刚好符合我们的假设.
后面的数字是我设计匹配成功的,
真实案例中,只是可能存在匹配成功,
但是这种平移已经能保证我们不会错过可能成功的案例
自我觉得平移的位数的原理已经讲得非常拎清了!
接下来就开始讲算法,
根据前面的原理,我们肯定是需要一个数组来保存最大匹配成功的公共字符串,然后还需要一个函数来计算这个公共字符串的最大公共前后缀好来决定平移几位.
using namespace std;
int main()
{
/*
目标字符串:asabusakswwlsaksaksawlsdkiis
匹配字符串:saksawl
*/
string deStr("asabusakswwlsaksaksawlsdkiis");
string keyStr("saksawl");
//1.先匹配,找到匹配到的最大字符串,需要一个字符串maxStr来保存
string maxStr("");
unsigned long 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;
return 0;
}
}
i += steps;
}
cerr << "匹配不成功";
return -1;
}
我们可以看到,上面还有一个关键的函数,getNext(maxStr)还没有实现,这个函数告诉我们每次需要平移多少位.我已经用星号标出来啦.
接下来重中之重,俺们怎么实现这个函数getNext(maxStr)
unsigned long getNext(string maxStr){
string::size_type 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;
}
这个可能跟网络上的版本有些不同,因为代码都是基于我前面的理解,这些当然可以优化,但我只负责解释清楚kmp算法到底干啥了.
最后,本文如果有些错误请指出,我们共同进步!
