淺析KMP算法中next數(shù)組值計(jì)算

姚秀情

摘要：本文以實(shí)例出發(fā)分析了模式匹配kmp 算法以及算 法中next 函數(shù)的含義即形成過(guò)程，由定義出發(fā)，給出詳實(shí)的參數(shù)來(lái)判定k的情況來(lái)計(jì)算next數(shù)組的值，從另一個(gè)角度更好的幫助學(xué)生理解該算法。

關(guān)鍵詞：字符串匹配;kmp算法;next數(shù)組

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2019）03-0131-02

0 引言

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)一門非常重要的基礎(chǔ)課程，KMP算法——字符串匹配算法是經(jīng)典的算法，它指的是找出特定的模式串在一個(gè)較長(zhǎng)的字符串中出現(xiàn)的位置[1]。其算法的主要核心是next數(shù)組值的計(jì)算，利用模式串對(duì)應(yīng)的next 數(shù)組值，避免了匹配不成功時(shí)不必要的回溯，計(jì)算next數(shù)組的值對(duì)于初學(xué)者來(lái)說(shuō)其過(guò)程晦澀難懂。

1 BF算法與kmp算法

1.1 BF算法簡(jiǎn)介

傳統(tǒng)的BF算法為：如果當(dāng)前字符匹配成功（即S[i]==P[j]），則i++，j++，繼續(xù)匹配下一個(gè)字符;如果失配（即S[i]！=P[j]），令i=i-（j-1），j=0。相當(dāng)于每次匹配失敗時(shí)，i回溯，j被置為1。如有字符串S：iloveplay和模式串T：ilovx來(lái)說(shuō)利用BF算法匹配到s[5]和t[5]時(shí)，i回溯至2，j被置為1表現(xiàn)出BF算法的致命的缺點(diǎn)例子，如表格1所示。

1.2 kmp算法的基本思想

用kmp算法的基本思想可以實(shí)現(xiàn)當(dāng)S串iloveplay與T串ilovx在s[5]和t[5]失配時(shí)，直接用T[1]號(hào)元素與s串失配的字符s[5]進(jìn)行匹配，因?yàn)閕1=j1i2=j2i3=j3以此類推在i5≠j5失配之前都是兩兩相等的，且觀察s串自身來(lái)說(shuō)i1≠i2i2≠i3i3≠i4i4≠i5由此證明就j1≠i2j1≠i3j1≠i4，所以相對(duì)于S串有效地多往后面跳3個(gè)字符，加快了匹配速度，可以看出i是不需要回溯的，只需要回溯j就可以[2]，如表格2所示。

2 next數(shù)組描述

KMP算法防止了不必要的回溯不發(fā)生，它可以在匹配過(guò)程中失配的情況下，有效地多往后面跳幾個(gè)字符，加快匹配速度。而子串中每一個(gè)元素隨時(shí)都有可能發(fā)生不匹配的情況，當(dāng)發(fā)生不匹配時(shí)該用子串的哪個(gè)元素去和主串匹配就是我們所說(shuō)的next[j]數(shù)組，他指導(dǎo)著模式匹配下一步改用第幾號(hào)元素去進(jìn)行匹配。而模式串next數(shù)組值取決于模式串自身的特點(diǎn)，與被匹配的主串無(wú)關(guān)。

傳統(tǒng)的next數(shù)組使用遞推的思想，對(duì)于模式串T，且已知next[j]=k即T0Tk-1”=“Tj-kTj-1”時(shí)，next[j+1]=next[j]+1=k+1，但T0Tk-1Tk”≠ “Tj-kTj-1Tj”。換言之，當(dāng)Tk！=Tj時(shí)，有長(zhǎng)度為k+1的相同前綴后綴，不能再簡(jiǎn)單的令：next[j+1]=next[j]+1，這時(shí)若能在前綴“T0Tk-1Tk”中不斷的遞歸k=next[k]，找到一個(gè)字符Tk使得Tk=Tj，且滿足T0Tk'-1 Tk'=Tj-k'Tj-1Tj，從而next[j+1]=k+1=next[k']+1，否則next[j+1]=0。運(yùn)用這個(gè)思想對(duì)字符串“edeedee”求出的next數(shù)組值為0，1，1，2，2，3，4從描述過(guò)程不難看出其抽象難懂，極易造成錯(cuò)誤的結(jié)果。

3 next數(shù)組的定義法求解函數(shù)值

KMP算法相比于樸素的模式匹配算法，其改進(jìn)之處在于：利用已經(jīng)得到的“部分匹配”結(jié)果將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的距離[3]。設(shè)模式串為T1T2……Tj，，next函數(shù)的定義如下：

該方法嚴(yán)格從next數(shù)組的定義出發(fā)，模式串的下標(biāo)j從1開(kāi)始，當(dāng)下標(biāo)為1時(shí)，next[1]=0，當(dāng)下標(biāo)不為1時(shí)，根據(jù)模式串中字符的下標(biāo)j確定k的取值范圍，即1

4 結(jié)語(yǔ)

next數(shù)組代表了模式串與主串匹配失敗時(shí)模式串向前滑動(dòng)的距離數(shù)，在KMP算法中至關(guān)重要，本文重點(diǎn)闡述了由next數(shù)組的定義出發(fā)，給出了相應(yīng)的判定方法及要點(diǎn)分析，計(jì)算出了next數(shù)組的值，與遞推方法計(jì)算next數(shù)值完全吻合，在計(jì)算next數(shù)組值時(shí)提高了效率也方便理解。

參考文獻(xiàn)

[1] 程杰.大話數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2011.

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

[3] 左飛.算法之美隱匿在數(shù)據(jù)結(jié)構(gòu)背后的原理C++版[M].北京：電子工業(yè)出版社，2016.

Analysis of Next Array Value Computing in KMP Algorithms

YAO Xiu-qing

（Information Engineering College of Yango University，F(xiàn)uzhou? Fujian? 350015）

Abstract：This paper analyses the meaning of the pattern matching KMP algorithm and the next function in the algorithm， that is， the formation process. Starting from the definition， it gives detailed parameters to determine K to calculate the value of the next array， which can help students better understand the algorithm from another angle.

Key words：string matching; KMP algorithm; next array