基于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]。……