一種基于KMP算法思想的字符串匹配算法的研究與實現

孫娟紅

摘要：KMP算法在使用中效率很高，并且在失敗匹配之后，不必要重新進行內容字符的匹配，降低了匹配的速度和次數，使得效率大大提高。在本文中，主要是分析了該算法的優點和實現。

關鍵詞：KMP算法思想;字符;串匹配算法;研究;實現

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）26-0196-02

開放科學（資源服務）標識碼（OSID）：

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

1 BF算法

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

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

2 KMP模式匹配算法

2.1 算法前瞻

在應用KMP算法的時候，如果匹配失敗，不用再重新及西寧匹配和排列，使匹配次數有效減少，促進了效率的提高，這也是其主要的優勢所在。該算法主要是依靠move數組進行實現，在move數組中，包含了大量的關鍵字串。

參考圖2，我們進行了例子，將KMP算法和BF算法進行綜合的對比，其中就能夠看出在KMP算法中，其主要的優勢。假定存在有一個內容串C，還有另外一個關鍵字串K，K=”abcac”，在比較第二個字符的時候，容易產生失配，即C[2]！=K[2]。

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

從上面的圖3中就可以發現，如果對C[6]-K[4]進行比較的時候，就會發生配比失效的情況。而按照KMP思想只需要比較C[6]與K[1]就可以，如下圖所示。

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

2.2 算法思想

通過上述的研究得知，實際在開展匹配的時候，當出現失敗的情況，那么就只針對關鍵字串K，追溯其初始位置，而在內容串中，其比較位置是往后進行，不會存在重復。

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

在KMP算法使用中，最主要的是其move數組，對move數組的有效利用，能夠確保在失配前提下，進行關鍵字串的移動，并選擇移動的范圍和位數，從而減少匹配時間。應用KMP思想，就需要充分考慮怎么做好移位的工作?？梢酝ㄟ^move數組，當在內容串的時候，匹配的是關鍵字的串字符，就需要同時移動兩者下標。當匹配失敗的情況發生時，那么需要move數組，實現關鍵字串的有效移動。

2.3 求解move數組

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

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

2.4 move數組求解算法

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

3 在項目中算法的應用和實現分析

3.1 KMP模式匹配算法

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

4 結束語

綜上所述，本文通過研究BF算法，分析了KMP的算法思想，并對其應用優勢進行了總結分析。而且，對于KMP算法中的實現對策進行了闡述，進一步解答了move數組求解。當字符集較大時，針對BF算法和KMP算法進行對比和分析，利用KMP算法，不管是在精確度還是效率上，都遠遠強于BF算法?；谶@一情況，在對KMP算法應用的時候，一定要充分考慮實際情況，盡可能提高匹配效率，擴大應用范圍。

通過分析算法可以得知，能夠通過比較各個算法的效率和過程發現不同算法的特點和優勢，從而能夠進行自己算法的有效選擇，掌握能夠遵循的主要方式，在日常的學習和生活中進行廣泛的應用。

參考文獻：

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

[2] 韋安壘，李開科，張榆.一種快速單模式匹配算法的設計與實現[J].網絡空間安全，2018，9（1）：86-92.

[3] 吳同，李思其，楊衛軍，等.基于KMP算法的云存儲數據取證方法研究[J].信息網絡安全，2017（12）：36-39.

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

[5] 任平紅，陳矗.數據結構中模式匹配算法的教學方法探討[J].電腦知識與技術，2017，13（27）：173-174.

[6] 蔡婷，楊衛帥.一種改進的字符串模式匹配算法[J].物聯網技術，2017，7（7）：89-91，95.

【通聯編輯：唐一東】