基于KMP算法的next數(shù)組

陳子軒

摘要：該文主要敘述了基于KMP算法的next數(shù)組的理解，分析了在C++環(huán)境中利用next數(shù)組對(duì)KMP算法的具體實(shí)現(xiàn)，使該算法更加方便實(shí)用。

關(guān)鍵詞：KMP算法；next數(shù)組；匹配

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）03-0066-01

1 概述

字符串匹配是現(xiàn)代科學(xué)中的基本問題，如文獻(xiàn)目錄檢索系統(tǒng)與生物基因序列匹配工程。對(duì)于這一問題的研究，D.E.Knuth，J.H.Morris和V.R.Pratt改進(jìn)了Brute-Force算法，提出一種線性時(shí)間復(fù)雜的字符串匹配算法——KMP算法，該算法利用了上一次匹配失敗的反饋信息，通過模式串對(duì)應(yīng)的next數(shù)組減少回溯，成功地將時(shí)間復(fù)雜度由O（m*n）降低至O（m+n），從而達(dá)到快速匹配。

2 next數(shù)組的定義

next數(shù)組作為KMP算法中的關(guān)鍵，其特點(diǎn)是模式串每一位對(duì)應(yīng)的next值僅依賴模式串本身，而與主串無關(guān)。普遍定義[1]如下：

[next[j]=-1 j=0max{k|1≤k

其中模式串T（T0T1…Tm，m≥0）中每一個(gè)Tj （0≤j≤m）對(duì)應(yīng)的next值以next[j]表示。

3 next數(shù)組的理解

1）由next數(shù)組的定義可知，每個(gè)模式串都有對(duì)應(yīng)的唯一確定的next數(shù)組。對(duì)next數(shù)組可從兩個(gè)方面來理解：next數(shù)組是用來記錄字符串匹配過程中匹配失敗情況下可以向前多跳幾個(gè)字符（模式串本身局部匹配的信息）；next數(shù)組是用來描述模式串的對(duì)稱程度的，數(shù)組的值越大，對(duì)稱程度越高。

2） next數(shù)組的實(shí)現(xiàn)采用了遞推思想，即以賦值定義next[0]=0為起點(diǎn)，通過next[0]算出next[1]的值，進(jìn)而得到next[2]、next[3]、……、next[i]的值。

假設(shè)已求得next[j]=k，根據(jù)定義可得”T0T1…Tk-1”=” Tj-kTj-k+1 …Tj-1”，那么求next[j+1]的值可以分為以下兩種情況：

1°若Tk= Tj，則”T0T1…Tk”=” Tj-kTj-k+1 …Tj”，并且不可能存在k>k滿足上式，那么next[j+1]=k+1，即next[j+1]=next[j]+1。

2°若Tk！= Tj，則”T0T1…Tk”！=” Tj-kTj-k+1 …Tj”。設(shè)k=k1時(shí)，滿足Tk1=Tj，下求k1。

圖1 圖2

由圖1可知實(shí)際上就是將模式串T往右移，移動(dòng)后T的j對(duì)應(yīng)T的k1。

考慮另一個(gè)前提條件：”T0T1…Tk1-1”=” Tj-k1Tj-k1+1 …Tj-1”。實(shí)際上k1=next[k]，但滿足了上述條件不一定就滿足Tk1=Tj。也就是說僅移動(dòng)一次不一定滿足Tk1=Tj。如果移動(dòng)一次后得到k1仍然不滿足Tk1=Tj，就要按照前提條件再移動(dòng)一次。

由圖2，依此類推，直到Tkn=Tj或kn=0為止。此時(shí)有next[j+1]= kn+1，而kn=next[kn-1]且k1=k=next[j]，由于kn

4 有關(guān)next數(shù)組的題目解法

例.在KMP模式匹配算法中，需要求解串中P的next函數(shù)值，其定義如下（其中j為模式中符號(hào)的序號(hào)）。對(duì)于模式串”abaabaca”，其next函數(shù)值序列為多少。

[next[j]=0 j=1max{k|1

解 首先把字符串填入到一個(gè)表格中，

將j導(dǎo)入next函數(shù)，即可求解。

如j=1時(shí)，next[1]=0； j=2時(shí)，1

（上接第66頁）

即”ab”=”ba”，不成立，舍去。再取k=2（T1=T3），即”a”=”a”，成立。于是max{k}=2，即next[4]=2；

同理可得next數(shù)組中其他元素的值。

所以結(jié)果為：

5 next數(shù)組在C++環(huán)境下的實(shí)現(xiàn)

通過遞推思想得到的計(jì)算next數(shù)組算法用C++語言描述如下：

void makeNext（const char P[]，int next[]）

{int q，k，m=strlen（P）；

next[0]=0；

for（q=1，k=0；q

{while（k>0&&P[q]！=P[k]） k=next[k-1]；

if（P[q]==P[k]） k++；

next[q]=k； }}

6 總結(jié)

本文重點(diǎn)解釋了next數(shù)組的原理。next數(shù)組在模式串與主串匹配失敗時(shí)可索引模式串向前滑動(dòng)的距離數(shù)，在KMP算法中至關(guān)重要，并給出C++語言下next數(shù)組的代碼，以具體實(shí)現(xiàn)。

參考文獻(xiàn)：

[1] 王紅梅， 胡明， 王濤.數(shù)據(jù)結(jié)構(gòu)（C++版）[M].北京：清華大學(xué)出版社，2011.

[2] 湯亞玲. KMP算法中next數(shù)組的計(jì)算方法研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2009， 19（6）：98-101.

[3] 楊薇薇， 廖翔. 一種改進(jìn)的BM模式匹配算法[J]. 計(jì)算機(jī)應(yīng)用， 2006， 26（2）：318-319.