kmp算法详解..docxVIP

引记 此前一天，一位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算法的第二篇文章为：/v_JULY_v/archive/2011/06/15/6545192.aspx六（续）、从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算法要回溯，其代码如下：/v_july_v/article/details/7041827view plainint?Index(SString?S,?SString?T,?int?pos)?{???//返回T在S中第pos个字符之后的位置??i=pos;?j=1;k=0;???while?(?i?=?S[