淺論《數(shù)據(jù)結(jié)構(gòu)》中KMP模式匹配算法講解

楊凌雪 田宏兵

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

關(guān)鍵詞：模式匹配 ?next數(shù)組 ?KMP算法講解

中圖分類號(hào)：TP311.12-4 ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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第一次出現(xiàn)在字符串t中的起始位置。計(jì)算機(jī)科學(xué)研究最廣泛，最古老的問題之一就是字符串匹配。關(guān)于字符串的模式匹配，《數(shù)據(jù)結(jié)構(gòu)》教材中一般介紹兩種方法：一是“樸素的模式匹配算法”，另外一個(gè)是“快速模式匹配算法”，也就是KMP算法[1]。在教學(xué)過程中，KMP算法不易理解，特別是關(guān)于next數(shù)組的計(jì)算和作用部分，如果沒有合適的理論推導(dǎo)方法及例子，教師在講解的過程中會(huì)感覺事倍功半。因此，該文討論如何講好KMP算法。

1 ?樸素模式匹配算法

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

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

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

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

2 ?KMP算法

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

KMP算法解決了上述問題。

2.1 next數(shù)組

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

先看如下式子。

模式串p存在某個(gè)k（0

那么next[j]=k。

例如：

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

歸納一下，next[j]數(shù)組定義如下：

現(xiàn)舉例說明。

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

我們規(guī)定，next[0]=-1，next[1]=0（因p[1]前只有一個(gè)字符）。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]前只有一個(gè)字符a和p開頭的字符a相同，故next[6]=1。以此類推。

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

void getnext（seqstring p，int next[]）

{ ?int ?i ，j;