淺論《數據結構》中KMP模式匹配算法講解

楊凌雪 田宏兵

摘 ?要：模式匹配是《數據結構》中關于字符串的一個基本運算，一般有兩種方法，分別為“樸素算法”與“KMP算法”。KMP算法是一種高效的字符匹配算法，它的關鍵在于當字符匹配失敗以后，利用next數組中的信息使指針不需要回退，這樣就減少了匹配的次數，提高效率。KMP算法不容易理解，該文通過舉例等方法分析KMP算法的匹配原理及過程。

關鍵詞：模式匹配 ?next數組 ?KMP算法講解

中圖分類號：TP311.12-4 ? 文獻標識碼：A 文章編號：1672-3791（2019）07（a）-0196-03

Abstract： Pattern matching is a basic operation on strings in Data Structure. There are generally two methods， namely "simple algorithm" and "KMP algorithm". The KMP algorithm is an efficient character matching algorithm. The key is that the information in the next array is used to make the pointer don't need to be rolled back when the character matching fails， thus reducing the number of matching and improving efficiency. The KMP algorithm is not easy to understand. This paper analyzes the matching principle and process of KMP algorithm by examples.

Key Words： Pattern matching; Next array; KMP algorithm explanation

字符串的模式匹配，即找尋字符串p第一次出現在字符串t中的起始位置。計算機科學研究最廣泛，最古老的問題之一就是字符串匹配。關于字符串的模式匹配，《數據結構》教材中一般介紹兩種方法：一是“樸素的模式匹配算法”，另外一個是“快速模式匹配算法”，也就是KMP算法[1]。在教學過程中，KMP算法不易理解，特別是關于next數組的計算和作用部分，如果沒有合適的理論推導方法及例子，教師在講解的過程中會感覺事倍功半。因此，該文討論如何講好KMP算法。

1 ?樸素模式匹配算法

樸素的模式匹配算法的基本思想是：逐個使用p中的字符去與t中的字符進行比較，如圖1所示。

其中正文t的長度用n表示，模式字符串p的長度用m表示。如果t1=p1，t2=p2，…，tm=pm，則模式匹配成功，p1p2…pm即為所要尋找的子串，此時返回其起始位置1即可;否則，將p向右移動一個字符，然后用p中的字符從頭開始與t里面對應的字符一一比較[2]，如圖2所示。

重復此操作直到匹配成功，或p已移動到這樣一個位置：t中剩余字符數小于p長度，那么就表明模式匹配不成功，t中沒有子串與p相等，我們約定返回-1。

樸素模式匹配算法理解起來簡單，算法也易于實現，但因其執行效率低，最壞情況下時間復雜度為O（nm）。分析該算法我們知道，效率低的原因在于，尋求匹配時，沒有充分利用部分匹配的結果，每次比較不匹配時，模式p總是只能向右移動一個字符的位置，存在大量回溯。

2 ?KMP算法

在進行字符串比較時，能否在匹配不成功時不從頭開始匹配？部分匹配的信息可否記錄下來加以使用？要求不回溯，模式就需要向右滑動一段距離，那么又如何確定滑動多遠的距離呢？

KMP算法解決了上述問題。

2.1 next數組

next[j]指p[j]字符前有多少個字符與p開頭的字符相同。KMP算法中，模式p部分匹配的信息記錄在next數組中，因此next數組確定了模式p向右滑動的距離。教學過程中，next數組的定義、作用、數組元素的獲取和使用方法是字符串模式匹配章節講述的關鍵。

先看如下式子。

模式串p存在某個k（0

那么next[j]=k。

例如：

模式p=abcabcd，j=6時，p0p1p2=p3p4p5，說明p[6]前面有3個字符與模式開頭的3個字符相同，所以有next[6]=3。

歸納一下，next[j]數組定義如下：

現舉例說明。

p=ababaaabab，next[j]數組為表1所示。

我們規定，next[0]=-1，next[1]=0（因p[1]前只有一個字符）。p[2]前的字符b和p開頭的字符a不同，故next[2]=0。p[3]前的字符a和p開頭的字符a相同，故next[3]=1。p[4]前的字符ab和p開頭的字符ab相同，故next[4]=2。p[5]前的字符aba和p開頭的字符aba相同，故next[5]=3。p[6]前只有一個字符a和p開頭的字符a相同，故next[6]=1。以此類推。

明白了next數組的含義，再來講解根據模式p求數組next值的程序，就容易理解了。求next數組的程序如下：

void getnext（seqstring p，int next[]）

{ ?int ?i ，j;