任平紅+陳矗

摘要：字符串是計(jì)算機(jī)處理文本編輯問題時(shí)經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)，其模式匹配算法是最常見的操作之一。常用的模式匹配算法有BF（Brute-Force）算法和KMP（Knuth-Morris-Pratt）算法。BF算法因匹配失敗時(shí)主串和模式串都回溯，在某些情況下效率較差。KMP算法經(jīng)優(yōu)化后目標(biāo)串無回溯，效率較高。文中分析了BF算法和KMP算法的教學(xué)方法，對(duì)于模式匹配的學(xué)習(xí)有一定的借鑒作用。

關(guān)鍵詞：模式匹配；BF算法；KMP算法；next函數(shù)

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）27-0173-02

1 概述

字符串是比較常用的特殊的線性結(jié)構(gòu)，元素類型限定為字符。在實(shí)際的工作中，字符串常被用來處理非數(shù)值問題。字符串的模式匹配是很常見的問題，例如文本編輯中的查找等操作。一般的模式匹配是確定模式串T在目標(biāo)串S中第一次完整出現(xiàn)的位置。常見的算法有樸素的BF算法和經(jīng)優(yōu)化以后的KMP算法。在教學(xué)過程中，由于BF算法思想簡單，學(xué)生理解起來比較容易，教學(xué)效果較好。但是KMP算法思想較為復(fù)雜，部分學(xué)生對(duì)KMP算法的理解不夠深刻，特別是對(duì)其理論推導(dǎo)過程認(rèn)識(shí)模糊，對(duì)于模式匹配函數(shù)next的計(jì)算掌握的不牢固。針對(duì)以上問題，筆者結(jié)合多年的教學(xué)經(jīng)驗(yàn)，對(duì)兩種模式匹配算法的教學(xué)方法進(jìn)行了分析和總結(jié)，對(duì)于教學(xué)有一定的借鑒作用。

2 BF算法

2.1 基本思想

BF算法被稱為簡單的、樸素的模式匹配算法。目標(biāo)串S和模式T都從第1個(gè)字符開始匹配，如果成功則繼續(xù)匹配下一個(gè)字符；如果匹配失敗，則開始新的一趟匹配，目標(biāo)串回到匹配失敗這一趟開始位置的下一個(gè)位置，模式重新回到第1個(gè)字符。即如果S[i]和T[j]匹配失敗，則i=i-j+1，而j=0（采用順序結(jié)構(gòu)存儲(chǔ)字符串）。例如，某一趟匹配失敗時(shí)，字符串S[i-j]…S[i-1]=T[0]…T[j-1]，但是S[i]與T[j]不相等。此趟匹配方串從i-j開始，所以下一趟從i-j+1開始，模式指針j=0。

2.2 算法

2.3 效率分析

BF算法簡單明了，應(yīng)用比較廣泛。如果目標(biāo)串的長度為n，模式串的長度為m。最好情況為每趟匹配失敗都發(fā)生在模式的第一個(gè)字符。最好情況和平均情況下的時(shí)間復(fù)雜度均為O（m+n）。但是如果每趟匹配失敗都發(fā)生在模式的最后一個(gè)字符上，效率較差，時(shí)間復(fù)雜度為O（mn）。其原因在于匹配的過程中目標(biāo)串和模式的指針都回溯，各趟匹配之間是孤立的，下一趟匹配沒有充分利用前面部分匹配的結(jié)果。KMP算法為BF算法的改進(jìn)算法。

3 KMP算法

3.1 基本思想

KMP算法對(duì)BF算法做了很大的改進(jìn)。其出發(fā)點(diǎn)在于當(dāng)匹配失敗，要開始新的一趟匹配時(shí)，目標(biāo)串指針不回溯，而模式向右滑動(dòng)一段距離，其實(shí)是模式指針回溯。要實(shí)現(xiàn)此目標(biāo)，必須利用已有的部分匹配的結(jié)果。在教學(xué)過程中，除了利用實(shí)例說明問題外，還需要將其理論的推導(dǎo)公式向同學(xué)們講解清楚，這樣才能使學(xué)生真正理解KMP算法的精髓。KMP算法的核心在于如何確定模式向右滑動(dòng)的距離值k。模式T的每個(gè)位置匹配失敗時(shí)對(duì)應(yīng)的k值稱為next函數(shù)，用一維數(shù)組next[]表示。

3.2 理論推導(dǎo)

得到模式T的next函數(shù)之后，KMP算法的匹配過程和BF算法類似，不同之處在于當(dāng)匹配失敗時(shí)，主串的指針i不變，模式的指針j回到next[j]的位置上，從而實(shí)現(xiàn)了模式不回溯的目標(biāo)。

3.4 分析

與BF算法相比，KMP算法的先進(jìn)之處在于目標(biāo)串指針在匹配失敗時(shí)是不回溯的。雖然其平均的時(shí)間復(fù)雜度為O（n+m），但需要事先計(jì)算模式的next函數(shù)，并且算法的難度明顯增加，理解起來比較復(fù)雜。

4 總結(jié)

BF算法和KMP算法是字符串模式匹配的兩個(gè)重要算法。因BF算法的思想簡單，理解起來比較容易，學(xué)生一般對(duì)其掌握的較好。KMP算法對(duì)BF算法做了較大的改進(jìn)。當(dāng)匹配失敗時(shí)，目標(biāo)串指針不回溯，模式指針向右滑動(dòng)一段距離，而滑動(dòng)距離的大小由模式自身決定，與目標(biāo)串無關(guān)。KMP算法充分利用了已有的部分匹配的結(jié)果以及模式本身的特點(diǎn)，效率較高。但是其算法較為復(fù)雜，模式的next函數(shù)的計(jì)算以及匹配的過程都需要學(xué)生熟練掌握和應(yīng)用。即使如此，KMP算法的思想也非常值得借鑒，在教學(xué)過程中，需要將其理論推導(dǎo)過程向?qū)W生進(jìn)行深入而透徹的講解。同時(shí)結(jié)合具體的實(shí)例，向?qū)W生清楚明了地演示其匹配過程，從而達(dá)到較好的教學(xué)效果。

參考文獻(xiàn)：

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

[2] 安楊，趙波.模式匹配算法的教學(xué)探討[C].第24屆全國計(jì)算機(jī)新科技與計(jì)算機(jī)教育學(xué)術(shù)會(huì)議論文集，2013：121-125.

[3] 李萍，趙潤林.模式匹配算法的研究與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2017，13（18）：25-26.endprint