基于KMP算法Next数组的分析与优化

天地（常州）自动化股份有限公司 王晓波

基于KMP算法Next数组的分析与优化

天地（常州）自动化股份有限公司 王晓波

介绍了KMP算法的基本原理和实现方法，推导了Next数组的计算方法，分析了Next数组的缺陷，提出了修改方案，并且通过实例验证了算法的可行性和有效性。

KMP算法；Next数组；字符串匹配

1 KMP算法简述

字符串匹配是计算机科学中最古老、研究最广泛的问题之一。字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。其中，T称为文本，P称为模式，T和P都定义在同一个字母表上[1]。 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt共同发明的，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的[2]。具体实现就是实现一个Next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)[3]。

1.1 KMP算法基本原理

KMP算法是在暴力匹配算法基础上进行改进，从而大大提高了算法的效率。暴力匹配算法思路如下：

1)如果当前字符匹配成功（即T[i]==P[j]），则i++，j++，继续匹配下一个字符；

2)如果失配（即T[i]!=P[j]），令i=i-(j-1)，j=0。相当于每次匹配失败时，i回溯，j 被置为0。

这样做虽然可行，但是效率很差，因为要把"搜索位置"移到已经比较过的位置，重比一遍。一个基本事实是，当空格与D不匹配时，其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率[4]。

1.2 Next数组的作用

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表也称为Next数组。此也意味着在某个字符失配时，该字符对应的Next值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到Next[j]的位置）。如果Next[j]等于0或-1，则跳到模式串的开头字符，若Next[j]=k且k＞0，代表下次匹配跳到j之前的某个字符，而不是跳到开头，且具体跳过了k个字符。

2 计算Next数组

2.1 通过代码递推计算Next数组

问题的关键就是寻找模式串中最大长度的相同前缀和后缀，找到了模式串中每个字符之前的前缀和后缀公共部分的最大长度后，便可基于此匹配。而这个最大长度便正是Next数组要表达的含义：

1)如果对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相当于Next[j]= k；

2)若p[k]==p[j]，则Next[j+1]=Next[j]+1=k+1；

3)若p[k]≠p[j]，如果此时p[Next[k]]==p[j]，则Next[j+1]=Next[k]+1，否则继续递归前缀索引k=Next[k]，而后重复此过程。相当于在字符p[j+1]之前不存在长度为k+1的前缀"p0 p1,…,pk-1 pk"跟后缀“pj-k pjk+1,…,pj-1 pj"相等，那么是否可能存在另一个值t+1＜k+1，使得长度更小的前缀 “p0 p1,…,pt-1 pt” 等于长度更小的后缀“pj-t pj-t+1, …,pj-1 pj”呢？如果存在，那么这个t+1便是Next[j+1]的值，此相当于利用已经求得的Next数组（Next[0,...,k,...,j]）进行P串前缀跟P串后缀的匹配。

2.2 算法具体实现

下面，我们来基于Next数组进行匹配。给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，

1)最开始匹配时P[0]跟S[0]匹配失败

所以执行“如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j = Next[j]”，所以j=-1，故转而执行“如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），都令i++，j++”，得到i=1，j=0，即P[0]继续跟S[1]匹配。

P[0]跟S[1]又失配，j再次等于-1，i、j继续自增，从而P[0]跟S[2]匹配。

P[0]跟S[2]失配后，P[0]又跟S[3]匹配。

P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功，开始执行此条指令的后半段：“如果j = -1，或者当前字符匹配成功（即S[i]==P[j]），都令i++,j++”。

2)P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功,...,直到当匹配到P[6]处的字符D时失配（即S[10]!= P[6]），由于P[6]处的D对应的Next值为2，所以下一步用P[2]处的字符C继续跟S[10]匹配，相当于向右移动：j-Next[j]=6-2=4位。

3)向右移动4位后，P[2]处的C再次失配，由于C对应的Next值为0，所以下一步用P[0]处的字符继续跟S[10]匹配，相当于向右移动：j-Next[j]=2-0=2位。

4)移动两位之后，A跟空格不匹配，模式串后移1位。

5)P[6]处的D再次失配，因为P[6]对应的Next值为2，故下一步用P[2]继续跟文本串匹配，相当于模式串向右移动j-Next[j]=6-2=4位。

6)匹配成功，过程结束。

3 Next数组的优化

3.1 Next数组的缺陷

行文至此，咱们全面了解了暴力匹配的思路、KMP算法的原理、流程、流程之间的内在逻辑联系，以及Next数组的简单求解，最后基于《Next 数组》的匹配，看似洋洋洒洒，清晰透彻，但以上忽略了一个小问题。

比如，如果用之前的Next数组方法求模式串“abab”的Next数组，可得其Next数组为[-1 0 0 1]，当它跟文本串去匹配的时候，如果第二个b失配，于是模式串右移j-Next[j]= 3-1=2位。右移2位后，第一个b取代了上一步第二个b的位置，必然失配。问题出在哪呢？

3.2 Next数组的改进

问题出在不该出现p[j]=p[Next[j]]。为什么呢？理由是：当p[j]!=s[i]时，下次匹配必然是p[Next[j]]跟s[i]匹配，如果p[j]=p[Next[j]]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[Next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j]=p[Next[j]]。如果出现了p[j]=p[Next[j]]咋办呢？如果出现了，则需要再次递归，即令Next[j]=Next[Next[j]]。

只要出现了p[Next[j]]=p[j]的情况，则把Next[j]的值再次递归。例如在求模式串“abab”的第2个a的Next值时，如果是未优化的Next值的话，第2个a对应的Next值为0，相当于第2个a失配时，下一步匹配模式串会用p[0]处的a再次跟文本串匹配，必然失配。所以求第2个a的Next值时，需要再次递归：Next[2]=Next[Next[2]]=Next[0]=-1（此后，根据优化后的新Next值可知，第2个a失配时，执行“如果j=-1，或者当前字符匹配成功，都令i++,j++,继续匹配下一个字符” ），同理，第2个b对应的Next值为0。利用优化过后的Next数组求法，可知模式串“abab”的新Next数组为：[-1 0 -1 0]。

对于优化后的Next数组可以发现一点：如果模式串的后缀跟前缀相同，那么它们的Next值也是相同的，例如模式串abcabc，它的前缀后缀都是abc，其优化后的Next数组为：[-1 0 0 -1 0 0]，前缀后缀abc的Next值都为[-1 0 0]。

[1]S．Baluja．Population-based Incremental Learning[J]．Technical Report,CMU-CS-94-163,CarnegieMellon University,1994．

[2]严蔚敏,吴伟民．数据结构第二版[M．北京：清华大学出版社,1997：42．

[3]蒋文沛．对字符串模式匹配KMP算法的探讨[J]．广西民族师范学院学报,2001,08(02)：72-74．

[4]胡琨元,朱云龙,汪定伟．自适应KMP算法求解合同优化匹配问题[J]．系统工程,2004,22(12)：87-91．