一種基于KMP算法思想的字符串匹配算法的研究與實(shí)現(xiàn)

孫娟紅

摘要：KMP算法在使用中效率很高，并且在失敗匹配之后，不必要重新進(jìn)行內(nèi)容字符的匹配，降低了匹配的速度和次數(shù)，使得效率大大提高。在本文中，主要是分析了該算法的優(yōu)點(diǎn)和實(shí)現(xiàn)。

關(guān)鍵詞：KMP算法思想;字符;串匹配算法;研究;實(shí)現(xiàn)

中圖分類號(hào)：TP311? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）26-0196-02

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

當(dāng)前，我們處于信息化社會(huì)，巨大的信息量每天都充斥著人們的生活，不管是在哪個(gè)行業(yè)和領(lǐng)域中，文本都是承載信息的重要方式，信息的過濾和查找也成了主要的問題。查找字符串并過濾，如果設(shè)計(jì)不好那么就使得結(jié)果無法滿足人們的使用要求。所以說，高效率的處理過程就顯得尤為關(guān)鍵，隨著技術(shù)的發(fā)展逐漸產(chǎn)生了字符串查找和匹配功能。

1 BF算法

BF算法的理論很簡(jiǎn)單，就是從內(nèi)容串C第一個(gè)字符起始，到關(guān)鍵字串K的第一個(gè)字符，進(jìn)行挨個(gè)比較，在相等的情況下，進(jìn)進(jìn)入第二個(gè)字符的比較，之后后移，如果在哪個(gè)位置失配，那么就需要對(duì)關(guān)鍵字串K第一個(gè)字符和其內(nèi)容串中的第二個(gè)字符再進(jìn)行匹配和比較，然后類推。

存在K為關(guān)鍵字串、C為內(nèi)容串，表達(dá)式C=“xyxyy”， K=“xyy”，在C中匹配K。圖1即為整個(gè)的匹配的過程。在圖1中，即體現(xiàn)了BF算法的思想。BF算法的思維十分簡(jiǎn)單和直接，但是也存在很多的不足，例如內(nèi)容串定位中錯(cuò)誤，并且十分容易進(jìn)行重復(fù)的操作。在失配之后，需要進(jìn)行二次匹配，在這個(gè)過程中，我們需要先采用關(guān)鍵字串第一個(gè)字符，將其和內(nèi)容串第二個(gè)字符進(jìn)行對(duì)比，流程可以簡(jiǎn)化和省略，因?yàn)閷?duì)關(guān)鍵字串進(jìn)行觀察，發(fā)現(xiàn)其前邊的字符存在不相等性，并且在上輪的對(duì)比中，關(guān)鍵字串中的第二個(gè)字符于內(nèi)容串呈現(xiàn)相等的狀態(tài)，所以說，在關(guān)鍵字串中第一個(gè)字符和內(nèi)容串中第二個(gè)字符有著不相等性。在比較的過程中，如果避免這些重復(fù)比較過程，那么將會(huì)大大提高匹配的效率和水平，于是，KMP算法產(chǎn)生，在很大程度上彌補(bǔ)了BF算法存在的缺陷。

2 KMP模式匹配算法

2.1 算法前瞻

在應(yīng)用KMP算法的時(shí)候，如果匹配失敗，不用再重新及西寧匹配和排列，使匹配次數(shù)有效減少，促進(jìn)了效率的提高，這也是其主要的優(yōu)勢(shì)所在。該算法主要是依靠move數(shù)組進(jìn)行實(shí)現(xiàn)，在move數(shù)組中，包含了大量的關(guān)鍵字串。

參考圖2，我們進(jìn)行了例子，將KMP算法和BF算法進(jìn)行綜合的對(duì)比，其中就能夠看出在KMP算法中，其主要的優(yōu)勢(shì)。假定存在有一個(gè)內(nèi)容串C，還有另外一個(gè)關(guān)鍵字串K，K=”abcac”，在比較第二個(gè)字符的時(shí)候，容易產(chǎn)生失配，即C[2]！=K[2]。

根據(jù)過去的BF算法，在第二輪開始，需要針對(duì)內(nèi)容串第一個(gè)字符，并且針對(duì)關(guān)鍵字串第零個(gè)字符，在前邊標(biāo)注和說明。利用KMP算法，能夠今早了解到K串的特性，就是在開始的兩個(gè)字符中，存在不相等性，并且在第一輪中可知：C[1]=K[1]，C[0]=K[0]。從上面的表達(dá)式中就可以發(fā)現(xiàn)，K[0]=C[1]，所以可以省略這一比較環(huán)節(jié)，直接從k字符開始進(jìn)行比較，圖為第二輪比較詳情。

從上面的圖3中就可以發(fā)現(xiàn)，如果對(duì)C[6]-K[4]進(jìn)行比較的時(shí)候，就會(huì)發(fā)生配比失效的情況。而按照KMP思想只需要比較C[6]與K[1]就可以，如下圖所示。

從上述分析可知，在所有的環(huán)節(jié)中產(chǎn)生了三次重新匹配，并且匹配成功，并得出了有效的結(jié)論，提高了匹配的效率和水平。在以上的例子中，對(duì)方法只是進(jìn)行了大體的概括和分析，其方法的本質(zhì)該是什么，怎么樣能保障思路精確，如果實(shí)現(xiàn)最后代碼等等，這些問題都要進(jìn)行進(jìn)一步研究并解決。

2.2 算法思想

通過上述的研究得知，實(shí)際在開展匹配的時(shí)候，當(dāng)出現(xiàn)失敗的情況，那么就只針對(duì)關(guān)鍵字串K，追溯其初始位置，而在內(nèi)容串中，其比較位置是往后進(jìn)行，不會(huì)存在重復(fù)。

我們能夠得出：在使用KMP算法的時(shí)候，如果匹配失敗仍然可以了解關(guān)鍵字串的位置，并且能夠在失配位置進(jìn)行尋找和定位，然后再進(jìn)行比較，在整個(gè)算法過程中，對(duì)關(guān)鍵字串的重新定位和比較十分重要，并且這和內(nèi)容串的關(guān)系很小，幾乎不存在關(guān)系。

在KMP算法使用中，最主要的是其move數(shù)組，對(duì)move數(shù)組的有效利用，能夠確保在失配前提下，進(jìn)行關(guān)鍵字串的移動(dòng)，并選擇移動(dòng)的范圍和位數(shù)，從而減少匹配時(shí)間。應(yīng)用KMP思想，就需要充分考慮怎么做好移位的工作?？梢酝ㄟ^move數(shù)組，當(dāng)在內(nèi)容串的時(shí)候，匹配的是關(guān)鍵字的串字符，就需要同時(shí)移動(dòng)兩者下標(biāo)。當(dāng)匹配失敗的情況發(fā)生時(shí)，那么需要move數(shù)組，實(shí)現(xiàn)關(guān)鍵字串的有效移動(dòng)。

2.3 求解move數(shù)組

move數(shù)組概念定義：對(duì)于鍵字串K，如果和內(nèi)容串C在匹配過程中，有n個(gè)字符完成匹配，那么這些同時(shí)是在關(guān)鍵字串K中的前n個(gè)字符，對(duì)于該子串，我們利用tmp進(jìn)行綜合分析：

串tmp前后是否出現(xiàn)重復(fù)內(nèi)容，可以表示為單個(gè)字符重復(fù)，重復(fù)越多越好，只對(duì)重復(fù)最多的時(shí)候進(jìn)行記錄，對(duì)于該長度，在進(jìn)行重新匹配的過程中，無須進(jìn)行長度的重新測(cè)量，并且需要詳細(xì)記錄重復(fù)的間隔距離。當(dāng)這一距離出現(xiàn)配比失敗的時(shí)候，可以通過回溯長度的方式為關(guān)鍵字串K。所以，在對(duì)n下方匹配長度的時(shí)候，能夠有效提升效率。

2.4 move數(shù)組求解算法

代碼思路比較簡(jiǎn)單，其根本就是對(duì)關(guān)鍵字串和內(nèi)容串進(jìn)行的匹配，直到長度j，并得出匹配內(nèi)容tmp，之后對(duì)其進(jìn)行有效拆分，分為兩大部分，分別是前綴與后綴，而長度需要確保后綴更長。所以，對(duì)于后綴中是否出現(xiàn)前綴要密切進(jìn)行觀察，在前綴和后綴中，可以找出的重復(fù)最長值放在move[j]中。Move最開始的數(shù)據(jù)都是0，表示在關(guān)鍵字串中，已經(jīng)重新到頭部而且沒有發(fā)生偏移。

3 在項(xiàng)目中算法的應(yīng)用和實(shí)現(xiàn)分析

3.1 KMP模式匹配算法

就函數(shù)功能來看，是在KMP思想之下，進(jìn)行關(guān)鍵字串的確定和查找。即：匹配長度應(yīng)用的計(jì)數(shù)器是matchlen，并且在完成匹配字符之后的（37行）、（38行），對(duì)（43行）進(jìn)行計(jì)數(shù)。當(dāng)在（50行）出現(xiàn)失配的情況時(shí)，就表示長度為0，也就是在第一個(gè)字符中，就產(chǎn)生了不匹配，要對(duì)內(nèi)容串指針進(jìn)行后移，到（52行）。在（53行）中matchlen已經(jīng)記錄了完成匹配的字符，而move[matchlen]是指完成匹配matchlen個(gè)字符后前綴和后綴的出現(xiàn)狀態(tài)，在下次進(jìn)行比較的時(shí)候，就需要定位關(guān)鍵字串，之后就可以進(jìn)行move[matchlen]個(gè)長度的偏移。這里指的長度為跳過的長度，無法進(jìn)行重復(fù)對(duì)比，單也屬于匹配長度范疇，所以53行存在賦值。

4 結(jié)束語

綜上所述，本文通過研究BF算法，分析了KMP的算法思想，并對(duì)其應(yīng)用優(yōu)勢(shì)進(jìn)行了總結(jié)分析。而且，對(duì)于KMP算法中的實(shí)現(xiàn)對(duì)策進(jìn)行了闡述，進(jìn)一步解答了move數(shù)組求解。當(dāng)字符集較大時(shí)，針對(duì)BF算法和KMP算法進(jìn)行對(duì)比和分析，利用KMP算法，不管是在精確度還是效率上，都遠(yuǎn)遠(yuǎn)強(qiáng)于BF算法?；谶@一情況，在對(duì)KMP算法應(yīng)用的時(shí)候，一定要充分考慮實(shí)際情況，盡可能提高匹配效率，擴(kuò)大應(yīng)用范圍。

通過分析算法可以得知，能夠通過比較各個(gè)算法的效率和過程發(fā)現(xiàn)不同算法的特點(diǎn)和優(yōu)勢(shì)，從而能夠進(jìn)行自己算法的有效選擇，掌握能夠遵循的主要方式，在日常的學(xué)習(xí)和生活中進(jìn)行廣泛的應(yīng)用。

參考文獻(xiàn)：

[1] 余飛.模式匹配算法的分析與研究[J].電腦知識(shí)與技術(shù)，2018，14（10）：251-252.

[2] 韋安壘，李開科，張榆.一種快速單模式匹配算法的設(shè)計(jì)與實(shí)現(xiàn)[J].網(wǎng)絡(luò)空間安全，2018，9（1）：86-92.

[3] 吳同，李思其，楊衛(wèi)軍，等.基于KMP算法的云存儲(chǔ)數(shù)據(jù)取證方法研究[J].信息網(wǎng)絡(luò)安全，2017（12）：36-39.

[4] 王曉波.基于KMP算法Next數(shù)組的分析與優(yōu)化[J].電子世界，2017（20）：196，198.

[5] 任平紅，陳矗.數(shù)據(jù)結(jié)構(gòu)中模式匹配算法的教學(xué)方法探討[J].電腦知識(shí)與技術(shù)，2017，13（27）：173-174.

[6] 蔡婷，楊衛(wèi)帥.一種改進(jìn)的字符串模式匹配算法[J].物聯(lián)網(wǎng)技術(shù)，2017，7（7）：89-91，95.

【通聯(lián)編輯：唐一東】