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

天地（常州）自動(dòng)化股份有限公司 王曉波

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

天地（常州）自動(dòng)化股份有限公司 王曉波

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

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

1 KMP算法簡(jiǎn)述

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

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

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

1.2 Next數(shù)組的作用

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

2 計(jì)算Next數(shù)組

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

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

1)如果對(duì)于值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]，如果此時(shí)p[Next[k]]==p[j]，則Next[j+1]=Next[k]+1，否則繼續(xù)遞歸前綴索引k=Next[k]，而后重復(fù)此過程。相當(dāng)于在字符p[j+1]之前不存在長(zhǎng)度為k+1的前綴"p0 p1,…,pk-1 pk"跟后綴“pj-k pjk+1,…,pj-1 pj"相等，那么是否可能存在另一個(gè)值t+1＜k+1，使得長(zhǎng)度更小的前綴 “p0 p1,…,pt-1 pt” 等于長(zhǎng)度更小的后綴“pj-t pj-t+1, …,pj-1 pj”呢？如果存在，那么這個(gè)t+1便是Next[j+1]的值，此相當(dāng)于利用已經(jīng)求得的Next數(shù)組（Next[0,...,k,...,j]）進(jìn)行P串前綴跟P串后綴的匹配。

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

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

1)最開始匹配時(shí)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時(shí)失配（即S[10]!= P[6]），由于P[6]處的D對(duì)應(yīng)的Next值為2，所以下一步用P[2]處的字符C繼續(xù)跟S[10]匹配，相當(dāng)于向右移動(dòng)：j-Next[j]=6-2=4位。

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

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

5)P[6]處的D再次失配，因?yàn)镻[6]對(duì)應(yīng)的Next值為2，故下一步用P[2]繼續(xù)跟文本串匹配，相當(dāng)于模式串向右移動(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ù)組的簡(jiǎn)單求解，最后基于《Next 數(shù)組》的匹配，看似洋洋灑灑，清晰透徹，但以上忽略了一個(gè)小問題。

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

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

問題出在不該出現(xiàn)p[j]=p[Next[j]]。為什么呢？理由是：當(dāng)p[j]!=s[i]時(shí)，下次匹配必然是p[Next[j]]跟s[i]匹配，如果p[j]=p[Next[j]]，必然導(dǎo)致后一步匹配失?。ㄒ?yàn)閜[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個(gè)a的Next值時(shí)，如果是未優(yōu)化的Next值的話，第2個(gè)a對(duì)應(yīng)的Next值為0，相當(dāng)于第2個(gè)a失配時(shí)，下一步匹配模式串會(huì)用p[0]處的a再次跟文本串匹配，必然失配。所以求第2個(gè)a的Next值時(shí)，需要再次遞歸：Next[2]=Next[Next[2]]=Next[0]=-1（此后，根據(jù)優(yōu)化后的新Next值可知，第2個(gè)a失配時(shí)，執(zhí)行“如果j=-1，或者當(dāng)前字符匹配成功，都令i++,j++,繼續(xù)匹配下一個(gè)字符” ），同理，第2個(gè)b對(duì)應(yīng)的Next值為0。利用優(yōu)化過后的Next數(shù)組求法，可知模式串“abab”的新Next數(shù)組為：[-1 0 -1 0]。

對(duì)于優(yōu)化后的Next數(shù)組可以發(fā)現(xiàn)一點(diǎ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]蔣文沛．對(duì)字符串模式匹配KMP算法的探討[J]．廣西民族師范學(xué)院學(xué)報(bào),2001,08(02)：72-74．

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