KMP算法和BF算法.doc

KMP算法在介绍KMP算法之前,先介绍一下BF算法。,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。举例说明:S:ababcababaP:ababaBF算法匹配的步骤如下i=0i=1i=2i=3i=4第一趟:ababcababa第二趟:ababcababa第三趟:ababcababa第四趟:ababcababa第五趟:ababcababaababaababaababaababaababaj=0j=1j=2j=3j=4(i和j回溯)i=1i=2i=3i=4i=3第六趟:ababcababa第七趟:ababcababa第八趟:ababcababa第九趟:ababcababa第十趟:ababcababaababaababaababaababaababaj=0j=0j=1j=2(i和j回溯)j=0i=4i=5i=6i=7i=8第十一趟:ababcababa第十二趟:ababcababa第十三趟:ababcababa第十四趟:ababcababa第十五趟:ababcababaababaababaababaababaababaj=0j=0j=1j=2j=3i=9第十六趟:ababcababaababaj=4(匹配成功)代码实现:intBFMatch(char*s,char*p){inti,j;i=0;while(i<strlen(s)){j=0;while(s[i]==p[j]&&j<strlen(p)){i++;j++;}if(j==strlen(p))returni-strlen(p);i=i-j+1;//指针i回溯}return-1;}其实在上面的匹配过程中,有很多比较是多余的。在第五趟匹配失败的时候,在第六趟,i可以保持不变,j值为2。因为在前面匹配的过程中,对于串S,已知s0s1s2s3=p0p1p2p3,又因为p0!=p1!,所以第六趟的匹配是多余的。又由于p0==p2,p1==p3,所以第七趟和第八趟的匹配也是多余的。在KMP算法中就省略了这些多余的匹配。,就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(mn)下降到O(m+n)。在KMP算法中,为了确定在匹配不成功时,下次匹配时j的位置,引入了next[]数组,next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。对于next[]数组的定义如下:1)next[j]=-1j=02)next[j]=max(k):0<k<jP[0...k-1]=P[j-k,j-1]3)next[j]=0其他如:Pababaj01234next-10012即next[j]=k>0时,表示P[0...k-1]=P[j-k,j-1]因此KMP算法的思想就是:在匹配过程称,若发生不匹配的情况,如果next[j]>=0,则目标串的指针i不变,将模式串的指针j移动到next[j]的位置继续进行匹配;若next