KMP算法

从头到尾彻底理解KMP作者：July时间：最初写于2011年12月，2014年7月21日晚10点全部删除重写成此文，随后的半个多月不断反复改进。后收录于新书《编程之法：面试和算法心得》第4.4节中。1.引言本KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP，但苦于一直以来对KMP的理解始终不够，故才迟迟没有修改本文。然近期因开了个算法班，班上专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发在微博上。随后，一不做二不休，索性将PPT上的内容整理到了本文之中（后来文章越写越完整，所含内容早已不再是九张PPT那样简单了）。KMP本身不复杂，但网上绝大部分的文章（包括本文的2011年版本）把它讲混乱了。下面，咱们从暴力匹配算法讲起，随后阐述KMP的流程步骤、next数组的简单求解递推原理代码求解，接着基于next数组匹配，谈到有限状态自动机，next数组的优化，KMP的时间复杂度分析，最后简要介绍两个KMP的扩展算法。全文力图给你一个最为完整最为清晰的KMP，希望更多的人不再被KMP折磨或纠缠，不再被一些混乱的文章所混乱。有何疑问，欢迎随时留言评论，thanks。2.暴力匹配算法假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？如果用暴力匹配的思路，并假设现在文本串S匹配到i位置，模式串P匹配到j位置，则有：如果当前字符匹配成功（即S[i]==P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0。相当于每次匹配失败时，i回溯，j被置为0。理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：[cpp]viewplaincopyprint?1.intViolentMatch(char*s,char*p)2.{3.intsLen=strlen(s);4.intpLen=strlen(p);5.6.inti=0;7.intj=0;8.while(isLen&&jpLen)9.{10.if(s[i]==p[j])11.{12.//①如果当前字符匹配成功（即S[i]==P[j]），则i++，j++13.i++;14.j++;15.}16.else17.{18.//②如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=019.i=i-j+1;20.j=0;21.}22.}23.//匹配成功，返回模式串p在文本串s中的位置，否则返回-124.if(j==pLen)25.returni-j;26.else27.return-1;28.}举个例子，如果给定文本串S“BBCABCDABABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：1.S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）2.S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i=i-(j-1)，j=0”，i从2变到4，j一直为0）3.直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i]==P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）4.S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i]==P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去5.直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]!=P[j]），令i=i-(j-1)，j=0”，相当于S[5]跟P[0]匹配（i=5，j=0）6.至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5]=P[1]=B，而P[0]=A，即P[1]!=P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i不往回退，只需要移动j即可呢？答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i不回溯，通过修改j的位置，让模式串尽量地移动到有效的位置。3.KMP算法3.1定义Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法由DonaldKnuth、VaughanPratt、JamesH.Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：假设现在文本串S匹配到i位置，模式串P匹配到j位置o如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），都令i++，j++，继续匹配下一个字符；o如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j-next[j]位。换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置-失配字符对应的next值（next数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j-next[j]，且此值大于等于1。很快，你也会意识到next数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next[j]=k，代表j之前的字符串中有最大长度为k的相同前缀后缀。此也意味着在某个字符失配时，该字符对应的next值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next[j]的位置）。如果next[j]等于0或-1，则跳到模式串的开头字符，若next[j]=k且k0，代表下次匹配跳到j之前的某个字符，而不是跳到开头，且具体跳过了k个字符。转换成代码表示，则是：[cpp]viewplaincopyprint?1.intKmpSearch(char*s,char*p)2.{3.inti=0;4.intj=0;5.intsLen=strlen(s);6.intpLen=strlen(p);7.while(isLen&&jpLen)8.{9.//①如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），都令i++，j++10.if(j==-1||s[i]==p[j])11.{12.i++;13.j++;14.}15.else16.{17.//②如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]18.//next[j]即为j所对应的next值19.j=next[j];20.}21.}22.if(j==pLen)23.returni-j;24.else25.return-1;26.}继续拿之前的例子来说，当S[10]跟P[6]匹配失败时，KMP不是跟暴力匹配那样简单的把模式串右移一位，而是执行第②条指令：“如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]”，即j从6变到2（后面我们将求得P[6]，即字符D对应的next值为2），所以相当于模式串向右移动的位数为j-next[j]（j-next[j]=6-2=4）。向右移动4位后，S[10]跟P[2]继续匹配。为什么要向右移动4位呢，因为移动4位后，模式串中又有个“AB”可以继续跟S[8]S[9]对应着，从而不用让i回溯。相当于在除去字符D的模式串子串中寻找相同的前缀和后缀，然后根据前缀后缀求出next数组，最后基于next数组进行匹配（不关心next数组是怎么求来的，只想看匹配过程是咋样的，可直接跳到下文3.3.4节）。3.2步骤①寻找前缀后缀最长公共元素长度o对于P=p0p1...pj-1pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0p1...pk-1pk=pj-kpj-k+1...pj-1pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。举个例子，如果给定的模式串为“abab”，那么它的各个子串的前缀后缀的公共元素的最大长度如下表格所示：比如对于字符串aba来说，它有长度为1的相同前缀后缀a；而对于字符串abab来说，它有长度为2的相同前缀后缀ab（相同前缀后缀的长度为k+1，k+1=2）。②求next数组onext数组考虑的是除当前字符外的最长相同前缀后缀，所以通过第①步骤求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将第①步骤中求得的值整体右移一位，然后初值赋为-1，如下表格所示：比如对于aba来说，第3个字符a之前的字符串ab中有长度为0的相同前缀后缀，所以第3个字符a对应的next值为0；而对于abab来说，第4个字符b之前的字符串aba中有长度为1的相同前缀后缀a，所以第4个字符b对应的next值为1（相同前缀后缀的长度为k，k=1）。③根据next数组进行匹配o匹配失配，j=next[j]，模式串向右移动的位数为：j-next[j]。换言之，当模式串的后缀pj-kpj-k+1,...,pj-1跟文本串si-ksi-k+1,...,si-1匹配成功，但pj跟si匹配失败时，因为next[j]=k，相当于在不包含pj的模式串中有最大长度为k的相同前缀后缀，即p0p1...pk-1=pj-kpj-k+1...pj-1，故令j=next[j]，从而让模式串右移j-next[j]位，使得模式串的前缀p0p1,...,pk-1对应着文本串si-ksi-k+1,...,si-1，而后让pk跟si继续匹配。如下图所示：综上，KMP的next数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j处的字符跟文本串在i处的字符匹配失配时，下一步用next[j]处的字符继续跟文本串i处的字符匹配，相当于模式串向右移动j-next[j]位。接下来，分别具体解释上述3个步骤。3.3解释3.3.1寻找最长前缀后缀如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：也就是说，原模式串子串对应的各个前缀后缀的公共元素的最大长度表为（下简称《最大长度表》）：3.3.2基于《最大长度表》匹配因为模式串中首尾可能会有重复的字符，故可得出下述结论：失配时，模式串向右移动的位数为：已匹配字符数-失配字符的上一位字符所对应的最大长度值下面，咱们就结合之前的《最大长度表》和上述结论，进行字符串的匹配。如果给定文本串“BBCABCDABABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：1.因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配，所以不必考虑结论，直接将模式串不断的右移一位即可，直到模式串中的字符A跟文本串的第5个字符A匹配成功：2.继续往后匹配，当模式串最后一个字符D跟文本串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？因为此时已经匹配的字符