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

基于KMP算法Next數(shù)組的分析與優(yōu)化

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

介紹了KMP算法的基本原理和實現(xiàn)方法，推導(dǎo)了Next數(shù)組的計算方法，分析了Next數(shù)組的缺陷，提出了修改方案，并且通過實例驗證了算法的可行性和有效性。

KMP算法；Next數(shù)組；字符串匹配

1 KMP算法簡述

字符串匹配是計算機(jī)科學(xué)中最古老、研究最廣泛的問題之一。字符串匹配問題就是在一個大的字符串T中搜索某個字符串P的所有出現(xiàn)位置。其中，T稱為文本，P稱為模式，T和P都定義在同一個字母表上[1]。 KMP算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt共同發(fā)明的，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）。KMP算法的關(guān)鍵是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的[2]。具體實現(xiàn)就是實現(xiàn)一個Next()函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。時間復(fù)雜度O(m+n)[3]。

1.1 KMP算法基本原理

KMP算法是在暴力匹配算法基礎(chǔ)上進(jìn)行改進(jìn)，從而大大提高了算法的效率。暴力匹配算法思路如下：

1)如果當(dāng)前字符匹配成功（即T[i]==P[j]），則i++，j++，繼續(xù)匹配下一個字符；

2)如果失配（即T[i]!=P[j]），令i=i-(j-1)，j=0。相當(dāng)于每次匹配失敗時，i回溯，j 被置為0。

這樣做雖然可行，但是效率很差，因為要把"搜索位置"移到已經(jīng)比較過的位置，重比一遍。一個基本事實是，當(dāng)空格與D不匹配時，其實知道前面六個字符是"ABCDAB"。KMP算法的想法是，設(shè)法利用這個已知信息，不要把"搜索位置"移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率[4]。

1.2 Next數(shù)組的作用

怎么做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表也稱為Next數(shù)組。此也意味著在某個字符失配時，該字符對應(yīng)的Next值會告訴你下一步匹配中，模式串應(yīng)該跳到哪個位置（跳到Next[j]的位置）。如果Next[j]等于0或-1，則跳到模式串的開頭字符，若Next[j]=k且k＞0，代表下次匹配跳到j(luò)之前的某個字符，而不是跳到開頭，且具體跳過了k個字符。

2 計算Next數(shù)組

2.1 通過代碼遞推計算Next數(shù)組

問題的關(guān)鍵就是尋找模式串中最大長度的相同前綴和后綴，找到了模式串中每個字符之前的前綴和后綴公共部分的最大長度后，便可基于此匹配。而這個最大長度便正是Next數(shù)組要表達(dá)的含義：

1)如果對于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，相當(dāng)于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，否則繼續(xù)遞歸前綴索引k=Next[k]，而后重復(fù)此過程。相當(dāng)于在字符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]的值，此相當(dāng)于利用已經(jīng)求得的Next數(shù)組（Next[0,...,k,...,j]）進(jìn)行P串前綴跟P串后綴的匹配。

2.2 算法具體實現(xiàn)

下面，我們來基于Next數(shù)組進(jìn)行匹配。給定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，現(xiàn)在要拿模式串去跟文本串匹配，

1)最開始匹配時P[0]跟S[0]匹配失敗

所以執(zhí)行“如果j!=-1，且當(dāng)前字符匹配失敗（即S[i]!=P[j]），則令i不變，j = Next[j]”，所以j=-1，故轉(zhuǎn)而執(zhí)行“如果j=-1，或者當(dāng)前字符匹配成功（即S[i]==P[j]），都令i++，j++”，得到i=1，j=0，即P[0]繼續(xù)跟S[1]匹配。

P[0]跟S[1]又失配，j再次等于-1，i、j繼續(xù)自增，從而P[0]跟S[2]匹配。

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

P[0]跟S[3]再失配，直到P[0]跟S[4]匹配成功，開始執(zhí)行此條指令的后半段：“如果j = -1，或者當(dāng)前字符匹配成功（即S[i]==P[j]），都令i++,j++”。

2)P[1]跟S[5]匹配成功，P[2]跟S[6]也匹配成功,...,直到當(dāng)匹配到P[6]處的字符D時失配（即S[10]!= P[6]），由于P[6]處的D對應(yīng)的Next值為2，所以下一步用P[2]處的字符C繼續(xù)跟S[10]匹配，相當(dāng)于向右移動：j-Next[j]=6-2=4位。

3)向右移動4位后，P[2]處的C再次失配，由于C對應(yīng)的Next值為0，所以下一步用P[0]處的字符繼續(xù)跟S[10]匹配，相當(dāng)于向右移動：j-Next[j]=2-0=2位。

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

5)P[6]處的D再次失配，因為P[6]對應(yīng)的Next值為2，故下一步用P[2]繼續(xù)跟文本串匹配，相當(dāng)于模式串向右移動j-Next[j]=6-2=4位。

6)匹配成功，過程結(jié)束。

3 Next數(shù)組的優(yōu)化

3.1 Next數(shù)組的缺陷

行文至此，咱們?nèi)媪私饬吮┝ζヅ涞乃悸?、KMP算法的原理、流程、流程之間的內(nèi)在邏輯聯(lián)系，以及Next數(shù)組的簡單求解，最后基于《Next 數(shù)組》的匹配，看似洋洋灑灑，清晰透徹，但以上忽略了一個小問題。

比如，如果用之前的Next數(shù)組方法求模式串“abab”的Next數(shù)組，可得其Next數(shù)組為[-1 0 0 1]，當(dāng)它跟文本串去匹配的時候，如果第二個b失配，于是模式串右移j-Next[j]= 3-1=2位。右移2位后，第一個b取代了上一步第二個b的位置，必然失配。問題出在哪呢？

3.2 Next數(shù)組的改進(jìn)

問題出在不該出現(xiàn)p[j]=p[Next[j]]。為什么呢？理由是：當(dāng)p[j]!=s[i]時，下次匹配必然是p[Next[j]]跟s[i]匹配，如果p[j]=p[Next[j]]，必然導(dǎo)致后一步匹配失?。ㄒ驗閜[j]已經(jīng)跟s[i]失配，然后你還用跟p[j]等同的值p[Next[j]]去跟s[i]匹配，很顯然，必然失配），所以不能允許p[j]=p[Next[j]]。如果出現(xiàn)了p[j]=p[Next[j]]咋辦呢？如果出現(xiàn)了，則需要再次遞歸，即令Next[j]=Next[Next[j]]。

只要出現(xiàn)了p[Next[j]]=p[j]的情況，則把Next[j]的值再次遞歸。例如在求模式串“abab”的第2個a的Next值時，如果是未優(yōu)化的Next值的話，第2個a對應(yīng)的Next值為0，相當(dāng)于第2個a失配時，下一步匹配模式串會用p[0]處的a再次跟文本串匹配，必然失配。所以求第2個a的Next值時，需要再次遞歸：Next[2]=Next[Next[2]]=Next[0]=-1（此后，根據(jù)優(yōu)化后的新Next值可知，第2個a失配時，執(zhí)行“如果j=-1，或者當(dāng)前字符匹配成功，都令i++,j++,繼續(xù)匹配下一個字符” ），同理，第2個b對應(yīng)的Next值為0。利用優(yōu)化過后的Next數(shù)組求法，可知模式串“abab”的新Next數(shù)組為：[-1 0 -1 0]。

對于優(yōu)化后的Next數(shù)組可以發(fā)現(xiàn)一點：如果模式串的后綴跟前綴相同，那么它們的Next值也是相同的，例如模式串a(chǎn)bcabc，它的前綴后綴都是abc，其優(yōu)化后的Next數(shù)組為：[-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]嚴(yán)蔚敏,吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)第二版[M．北京：清華大學(xué)出版社,1997：42．

[3]蔣文沛．對字符串模式匹配KMP算法的探討[J]．廣西民族師范學(xué)院學(xué)報,2001,08(02)：72-74．

[4]胡琨元,朱云龍,汪定偉．自適應(yīng)KMP算法求解合同優(yōu)化匹配問題[J]．系統(tǒng)工程,2004,22(12)：87-91．