这个算法单纯从代码理解起来比较费劲.我觉得从思路上理解是非常简单的.
传统算法的劣势很容易察觉.那就是会有重复的匹配过程.我们假定 Text为待查文本, Pattern 为匹配串.
Text="aaaaB"
Pattern="aB"
按以下传统算法.则直到循环到最后一次比较.才找到"aB".而前面很多循环都是做的无用功.
#include#include typedef const char* const CSTR;int findStr(CSTR src,int from,CSTR des){ const char* p=src+from; while (*p) { const char* pStr1=p; const char* pDes=des; while (*pStr1 && *pStr1 == *pDes ) { pDes++; pStr1++; if(!*pDes ) return (pStr1-src-(pDes - des))/sizeof(char) ; } p++; } return -1;}
而kmp算法是想怎么思考的呢?
是这样.让Pattern字符串里的每一个字符都带上一个标示.来标示Pattern字符之间的关系.这些字符间的关系可以省下很多重复的比较.比如说
如果Pattern="ABCABCABC" Text="ABCABX"
模拟计算机比较过程,请把下面的字符串看成可左右移动的纸带.
黑体表示从左到右的比较,并相等.红色代表不相等发生处,维护两个下标.代表当前对比的字符串.我就不取名字了.免得你头晕.用彩色表示.此处为红色.
ABCABCABC
ABCABX
当计算到C与X不相等时.计算机该怎么做才最有效率呢?? 传统算法会这样,将Text的对比下标指向B.
ABCABCABC
ABCABX
KMP会怎样?KMP会这样...
ABCABCABC
ABCABX
所以KMP诡异在哪? 它为什么要跳过去.为什么要从Pattern[2]开始比较??而不是从头开始比较? 其实道理非常简单,我们先回到刚开始比较时候的情况
ABCABCABC
ABCABX
再具体看看Pattern
ABCABX 我将AB标蓝.而且加了下划线.为什么?因为他们是重复的!!!并且是与开头的串重复.!! 这种重复有什么性质呢?我们把开头的AB称为第一组.后面的AB为第二组.
ABCABCABC
ABCABX
如果在对比完第二组AB后,当C与X对比发现了不相同时.由于第一组AB与第二组AB是相同的, 在Text[5]与Pattern[5]对比不相同后,将第1组AB的位置替换第二组AB的位置.再进行下一个字符的比较. 上面示例的和下面示例的转换是对等的.而下面的下一步将是比较Text[5]与Pattern[2] 也即 也即比较C 与 C. 相等. 特别要注意的是Text下标在下一轮比较中下标未动.(橙色代表将要比较的字符,但还没比较 )
ABCABCABC
ABCABX
如果你看到,并理解了.其实你已经懂了KMP的核心思想了.只不过要将这个思想再具体化而已了.
首先要解决的一问题.我怎么知道在发现C与X不等时,让Pattern哪一位再来与C比较呢?从上面的示例可以看出.是Pattern[2].好.我们已经解决了一个问题了.那我们把2存哪呢??既然它与Pattern[5]相关,也即与X相关.我们建一个与Pattern一样长度的int数组.名叫Next[],指定Next[5]=2.
ABCABCABC
ABCABX
第二个问题随即而来,Next数组其他的数值填什么呢? 我们先想另外一个问题.那就是.我们什么时候会需要Next里的值?对了.那就是当Pattern与Text 在对比某值发生了不相等的时候.比如上面的C跟X.现在我们将Text改一下,Pattern保持不变,不然Next其他值用不到,KMP算法就结束了...:) 变成如下,
ABCBDCABC
ABCABX
当对比到Text[3]与 Pattern[3]时,发现了不同. 这个时候怎么移动Pattern呢? 很简单.如果你看出了规律! 请按你规律写算法即可.而我....太蠢没看出规律..所以.在Next[3]处.我将填入一个 -1 ,意思是, Pattern回到起点开始比较.而Text往后移一位.如下示..哦.为什么要移一位?? 首先我请问你一个问题.
ABCBDCABC
ABCABX
那就是,随你怎么改Text串.你能得到某个Text串使前面提到的移一位会出现错误吗?你会发现..永远不会..为啥 ? 我们来看一下Pattern串. 其中重复的AB.A为重复串的开头.这个信息看起来有点重要..的确如此.看上面Text[3]与Pattern[3]不等.在而Pattern[3]是一个特殊的值..它是重复串AB的第一个值.所以如果像下面所示.有意义么...?没有!! 肯定不等.(而且在算法里会产生死循环...动不了了...) 好了,我们现在又有了一个规则.重复串的开关必须为 -1 . 现在Next值又多了两个成员Next[0]= -1, Next[3] =-1; 再有一个Next[5] =2.在上文已提过.
ABCBDCABC
ABCABX
现在Next数组已经填了3个数了.貌似还剩下3个没填..怎么办!! 其实.很简单.如果你觉得没有再可以优化的地方了.你就直接调用传统查找算法.而核心思想就是Pattern 回到 0 位置.Text保持不动.至于怎么在Next里表示.那随你.~按我们现在的逻辑最好是写个0.代表回到Pattern[0].这样最好.但记住.还要保持Text别动.不是像 Next[k]=-1一样.向后移一位.
所以我们看看Next这个数组...是个什么东西?其实就是一个对Pattern规律的一个表示形式而已.我上面描述的规律还只总结了两条而已.你可以总结更多条,在算法中加已利用.我们总结了哪两条规则?
ABEEEABFABF 我们就拿这个做例子.我不喜欢说定理...一堆j k 参数看着头晕 ..
ABEEEABFABF 开头的重复与后面的重复找出来.将Next[0]=-1.将Next[5]=-1;将Next[8]=-1 ,将Next[7]=2 将Next[10]=2; Next其他的值填为0.
则得到.
Next[]={-1, 0, 0, 0, 0, -1, 0, 2, -1, 0, 2};
少年.你学会KMP了...你可以发挥你的才能继续扩展KMP.因为0放在那有些浪费 ....
给一个规则更多的求next的 函数 看它的if大概能猜到有4条规则..你可以想更多.
void genPattern(const char* const des,int ** pattern, int* size ){ *size=strlen(des); (*pattern)=new int[*size]; (*pattern)[0]=0; int j=1; int start=0; int same_from_beg=0; bool after_repeat_char=false; while (*(des+j)) { if( after_repeat_char) start++; else start=0; if (*(des+j)==*(des+start)) { (*pattern)[j]=0 ; same_from_beg++; if(*(des+j)==*(des)) after_repeat_char=false; else after_repeat_char=true; }else { if(after_repeat_char) (*pattern)[j]=same_from_beg; else (*pattern)[j]=-1; } j++; } }
再提供一个与之配套的KMP算法 ,将代码复制。自己跑跑，有可视化的console打印
int kmp(const char* src,const char * des ){ const char* p=src ; int * pattern, size,i=0, j=0; genPattern(des,&pattern,&size); while(*(p+i) ) { //debug print { printf("%s\n",src); for (int a=0;a
免费供应一个main函数 :)
1 abcabcx 2 | 3 abcx 4 5 abcabcx 6 || 7 abcx 8 9 abcabcx10 |||11 abcx12 13 abcabcx14 |||*15 abcx16 17 abcabcx18 |19 abcx20 21 abcabcx22 ||23 abcx24 25 abcabcx26 |||27 abcx28 29 abcabcx30 ||||31 abcx