基于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．