kmp算法详解

引记此前一天，一位MS的朋友邀我一起去与他讨论快速排序，红黑树，字典树，B树、后缀树，包括KMP算法，唯独在讲解KMP算法的时候，言语磕磕碰碰，我想，原因有二：1、博客内的东西不常回顾，忘了不少；2、便是我对KMP算法的理解还不够彻底，自不用说讲解自如，运用自如了。所以，特再写本篇文章。由于此前，个人已经写过关于KMP算法的两篇文章，所以，本文名为：KMP算法之总结篇。本文分为如下六个部分：1.第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度，并两相对照各自的匹配原理；2.第二部分、通过我此前第二篇文章的引用，用图从头到尾详细阐述KMP算法中的next数组求法，并运用求得的next数组写出KMP算法的源码；3.第三部分、KMP算法的两种实现，代码实现一是根据本人关于KMP算法的第二篇文章所写，代码实现二是根据本人的关于KMP算法的第一篇文章所写；4.第四部分、测试，分别对第三部分的两种实现中next数组的求法进行测试，挖掘其区别之所在；5.第五部分、KMP完整准确源码，给出KMP算法的准确的完整源码；6.第六步份、一眼看出字符串的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：aaaacefghijj++T：aaac如果不回溯的话就是从下一位开始比起：aaaacefghijaaac看到上面红颜色的没，如果不回溯的话，那么从a的下一位c比起。然而下述这种情况就漏了（正确的做法当然是要回溯：如果失配，即S[i+j]!=T[j]，需要让i++,并且j=0）：aaaacefghijaaac所以，BF算法要回溯，其代码如下：viewplain1.intIndex(SStringS,SStringT,intpos){2.//返回T在S中第pos个字符之后的位置3.i=pos;j=1;k=0;4.while(i=S[0]&&j=T[0]){5.if(S[i+k]==T[j]){++k;++j;}//继续比较后续字符6.else{i=i+1;j=1;k=0;}//指针回溯到下一首位，重新开始7.}8.if(jT[0])returni;//子串结束，说明匹配成功9.elsereturn0;10.}//Index不过，也有特殊情况可以不回溯，如下：abcdefghij(主串)abcdefg(模式串)即(模式串)没有相同的才不需要回溯。4、KMP算法思想普通的字符串匹配算法必须要回溯。但回溯就影响了效率，回溯是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。像上面所说如果主串为abcdef这样的，大没有回溯的必要。改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。如果不用回溯，那模式串下一个位置从哪里开始呢？还是上面那个例子，T(模式串)为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样：...ababd...ababc-ababc这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串(主串)无关。5、next数组的含义重点来了。下面解释一下next数组的含义，这个也是KMP算法中比较不好理解的一点。令原始串为:S[i]，其中0=i=n；模式串为:T[j]，其中0=j=m。假设目前匹配到如下位置S0,S1,S2,...,Si-j,Si-j+1...............,Si-1,Si,Si+1,....,SnT0,T1,.....................,Tj-1,Tj,..........S和T的绿色部分匹配成功，恰好到Si和Tj的时候失配，如果要保持i不变，同时达到让模式串T相对于原始串S右移的话，可以更新j的值，让Si和新的Tj进行匹配，假设新的j用next[j]表示，即让Si和next[j]匹配，显然新的j值要小于之前的j值，模式串才会是右移的效果，也就是说应该有next[j]=j-1。那新的j值也就是next[j]应该是多少呢？我们观察如下的匹配：1)如果模式串右移1位（从简单的思考起，移动一位会怎么样），即next[j]=j-1，即让蓝色的Si和Tj-1匹配(注：省略号为未匹配部分)S0,S1,S2,...,Si-j,Si-j+1...............,Si-1,Si,Si+1,....,SnT0,T1,.....................,Tj-1,Tj,..........(T的划线部分和S划线部分相等【1】)T0,T1,.................Tj-2,Tj-1,.......(移动后的T的划线部分和S的划线部分相等【2】)根据【1】【2】可以知道当next[j]=j-1，即模式串右移一位的时候，有T[0~j-2]==T[1~j-1]，而这两部分恰好是字符串T[0~j-1]的前缀和后缀，也就是说next[j]的值取决于模式串T中j前面部分的前缀和后缀相等部分的长度（好好揣摩这两个关键字概念：前缀、后缀，或者再想想，我的上一篇文章，从Trie树谈到后缀树中，后缀树的概念）。2)如果模式串右移2位，即next[j]=j-2，即让蓝色的Si和Tj-2匹配S0,S1,...,Si-j,Si-j+1,Si-j+2...............,Si-1,Si,Si+1,....,SnT0,T1,T2,.....................,Tj-1,Tj,..........(T的划线部分和S划线部分相等【3】)T0,T1,...............,Tj-3,Tj-2,.........(移动后的T的划线部分和S的划线部分相等【4】)同样根据【3】【4】可以知道当next[j]=j-2，即模式串右移两位的时候，有T[0~j-3]==T[2~j-1]。而这两部分也恰好是字符串T[0~j-1]的前缀和后缀，也就是说next[j]的值取决于模式串T中j前面部分的前缀和后缀相等部分的长度。3)依次类推，可以得到如下结论：当发生失配的情况下，j的新值next[j]取决于模式串中T[0~j-1]中前缀和后缀相等部分的长度，并且next[j]恰好等于这个最大长度。为此，请再允许我引用上文中的一段原文：“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++，否则此时没有移动模式串)。”于此，也就不难理解了我的关于KMP算法的第二篇文章之中：“当匹配到S[i]!=P[j]的时候有S[i-j…i-1]=P[0…j-1].如果下面用j_next去匹配，则有P[0…j_next-1]=S[i-j_next…i-1]=P[j-j_next…j-1]。此过程如下图3-1所示。当匹配到S[i]!=P[j]时，S[i-j…i-1]=P[0…j-1]：S:0…i-j…i-1i…P:0…j-1j…如果下面用j_next去匹配，则有P[0…j_next-1]=S[i-j_next…i-1]=P[j-j_next…j-1]。所以在P中有如下匹配关系（获得这个匹配关系的意义是用来求next数组）：P:0…j-j_next.…j-1_…P:0….j_next-1…所以，根据上面两个步骤，推出下一匹配位置j_next:S:0…i-j…i-j_next…i-1i…P:0…j_next-1j_next…图3-1求j-next（最大的值）的三个步骤下面，我们用变量k来代表求得的j_next的最大值，即k表示这S[i]、P[j]不匹配时P中下一个用来匹配的位置，使得P[0…k-1]=P[j-k…j-1]，而我们要尽量找到这个k的最大值。”。根据上文的【1】与【2】的匹配情况，可得第二篇文章之中所谓的k=1（如aaaa的形式），根据上文的【3】与【4】的匹配情况，k=2（如abab的形式）。所以，归根究底，KMP算法的本质便是：针对待匹配的模式串的特点，判断它是否有重复的字符，从而找到它的前缀与后缀，进而求出相应的Next数组，最终根据Next数组而进行KMP匹配。接下来，进入本文的第二部分。第二部分、next数组求法的来龙去脉与KMP算法的源码本部分引自个人此前的关于KMP算法的第二篇文章：六之续、由KMP算法谈到BM算法。前面，我们已经知道即不能让P[j]=P[next[j]]成立成立。不能再出现上面那样的情况啊！即不能有这种情况出现：P[3]=b，而竟也有P[next[3]]=P[1]=b。正如在第二篇文章中，所提到的那样：“这里读者理解可能有困难的是因为文中，时而next，时而nextval，把他们的思维搞混乱了。其实next用于表达数组索引，而nextval专用于表达next数组索引下的具体各值，区别细微。至于文中说不允许P=P[next[j]]出