kmp算法详解.docx

引记
    此前一天,一位MS的朋友邀我一起去与他讨论快速排序,红黑树,字典树,B树、后缀树,包括KMP算法,唯独在讲解KMP算法的时候,言语磕磕碰碰,我想,原因有二:1、博客内的东西不常回顾,忘了不少;2、便是我对KMP算法的理解还不够彻底,自不用说讲解自如,运用自如了。所以,特再写本篇文章。由于此前,个人已经写过关于KMP算法的两篇文章,所以,本文名为:KMP算法之总结篇。
   本文分为如下六个部分:
第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度,并两相对照各自的匹配原理;
第二部分、通过我此前第二篇文章的引用,用图从头到尾详细阐述KMP算法中的next数组求法,并运用求得的next数组写出KMP算法的源码;
第三部分、KMP算法的两种实现,代码实现一是根据本人关于KMP算法的第二篇文章所写,代码实现二是根据本人的关于KMP算法的第一篇文章所写;
第四部分、测试,分别对第三部分的两种实现中next数组的求法进行测试,挖掘其区别之所在;
第五部分、KMP完整准确源码,给出KMP算法的准确的完整源码;
第六步份、一眼看出字符串的next数组各值,通过几个例子,让读者能根据字符串本身一眼判断出其next数组各值。
    力求让此文彻底让读者洞穿此KMP算法,所有原理,来龙去脉,让读者搞个通通透透(注意,本文中第二部分及第三部分的代码实现一的字符串下标i 从0开始计算,其它部分如第三部分的代码实现二,第五部分,和第六部分的字符串下标i 皆是从1开始的)。
    在看本文之前,你心中如若对前缀和后缀这个两个概念有自己的理解,便最好了。有些东西比如此KMP算法需要我们反复思考,反复求解才行。个人写的关于KMP算法的第二篇文章为:六(续)、从KMP算法一步一步谈到BM算法;第一篇为:六、教你初步了解KMP算法、updated(文末链接)。ok,若有任何问题,恳请不吝指正。多谢。
第一部分、KMP算法初解
1、普通字符串匹配BF算法与KMP算法的时间复杂度比较
    KMP算法是一种线性时间复杂的字符串匹配算法,它是对BF算法(Brute-Force,最基本的字符串匹配算法的)改进。对于给的原始串S和模式串P,需要从字符串S中找到字符串P出现的位置的索引。
BF算法的时间复杂度O(strlen(S) * strlen(T)),空间复杂度O(1)。
KMP算法的时间复杂度O(strlen(S) + strlen(T)),空间复杂度O(strlen(T))。
2、BF算法与KMP算法的区别
    假设现在S串匹配到i位置,T串匹配到j位置。那么总的来说,两种算法的主要区别在于失配的情况下,对 的值做的处理:
   BF算法中,如果当前字符匹配成功,即s[i+j] == T[j],令j++,继续匹配下一个字符;如果失配,即S[i + j] != T[j],需要让i++,并且j= 0,即每次匹配失败的情况下,模式串T相对于原始串S向右移动了一位。
    而KMP算法中,如果当前字符匹配成功,即S[i]==T[j],令i++,j++,继续匹配下一个字符;如果匹配失败,即S[i] != T[j],需要保持i不变,并且让j = next[j],这里next[j] <=j -1,即模式串T相对于原始串S向右移动了至少1位(移动的实际位数j - next[j]  >=1),
    同时移动之后,i之前的部分(即S[i-j+1 ~ i-1]),和j=next[j]之前的部分(即T[0 ~ j-2])仍然相等。显然,相对于BF算法来说,KMP移动更多的位数,起到了一个加速的作用! (失配的特殊情形,令j=next[j]导致j==0的时候,需要将i ++,否则此时没有移动模式串)。
3、BF算法为什么要回溯
首先说一下为什么BF算法要回溯。如下两字符串匹配(恰如上面所述:BF算法中,如果当前字符匹配成功,即s[i+j] == T[j],令j++,继续匹配下一个字符):
      i+j(j随T中的j++变,而动)
S:aaaacefghij
         j++
T:aaac 
如果不回溯的话就是从下一位开始比起:
aaaacefghij
        aaac
看到上面红颜色的没,如果不回溯的话,那么从a 的下一位c 比起。然而下述这种情况就漏了(正确的做法当然是要回溯:如果失配,即S[i + j] != T[j],需要让i++,并且j= 0):
aaaacefghij
  aaac
    所以,BF算法要回溯,其代码如下:
view plain
int Index(SString S, SString T, int pos) {  
   //返