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

姚秀情

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

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

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9416（2019）03-0131-02

0 引言

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

1 BF算法與kmp算法

1.1 BF算法簡介

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

1.2 kmp算法的基本思想

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

2 next數(shù)組描述

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

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

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

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

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

4 結(jié)語

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

參考文獻

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

[2] 湯雅玲.KMP算法中next數(shù)組的計算方法研究[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