關(guān)于kmp算法改進的探討

摘要：本文以模式串t是否有重復的幾種不同情況的例子，分析了模式匹配算法kmp的形成過程，將較難理解的next函數(shù)的計算融入到算法中去，對算法做了一點改進，改進后的算法遵循kmp算法主串指針不回溯的原則，但卻更容易理解。

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

中圖分類號：TP301.6? ?文獻標識碼：A? ? 文章編號：1007-9416（2020）04-0000-00

1 引言

KMP算法是一種字符串比較算法，相對于BF算法，它有比較大的改進，也是一款經(jīng)典的算法，且它在計算機應(yīng)用系統(tǒng)中如文本編輯、情報檢索、自然語言翻譯有著廣泛的應(yīng)用[1]，是每一個想學習字符串匹配的人必須要了解的一個算法，但相信很多人初識KMP算法的時候都是知其然而不知其所以然，對于其next[j]數(shù)組更是一頭霧水。

2 kmp 算法的研究與分析

2.1 kmp算法的概述

對于樸素的模式匹配算法即BF算法，它的基本思想是：有主串s和模式串（子串）t，要求找出模式串t在s串中的首次出現(xiàn)的位置。若當前字符匹配成功（即s[i] == t[j]，i為主串的下標，j為模式串的下標），則i++，j++，繼續(xù)匹配下一個字符;如果失配（即s[i]！ = t[j]），令i回溯到 i-j+1的位置，j回到模式串起始字符位置，這樣的算法比較次數(shù)多，相當耗時。為了提高效率KMP算法對BF算法做了改進，其核心思想就是減少比較的次數(shù)即讓主串s沒必要的回溯不發(fā)生，它的最大改進在于在匹配過程中失配的情況下，將模式串t有效地多往后面跳幾個字符，加快匹配速度，那究竟能有效的往后面跳幾個字符來減少次數(shù)呢，kmp算法認為，匹配過程與模式串的特征關(guān)系密切，如果對于模式串中存在一個整數(shù)k（k

2.2 kmp算法的形成過程分析

在以下例子中s串的下標i與t串的下標j都是從1開始。

第一種情況是t串在失配字符前沒有重復字符的情況時：第一次匹配是s串iambabynigthowl與t串iambe在下標為5的元素失配時（即s[5]！=t[5]），直觀t串失配字符前的幾個元素發(fā)現(xiàn)并不相等，即t[1] ≠t[2] ≠ t[3] ≠t[4]，而在失配前s串與t串的前4個字符一一對應(yīng)，所以可以判斷出t[1]字符與s串的前四個字符都不相同，所以第二次比較直接將t[1]字符與s[5]字符開始比較即可，子串向右滑動了4個字符，相比于BF算法，s串的下標i沒有回到s[2]的位置重新與t[1]字符開始比較，比較次數(shù)減少了三次。

第二種情況是t串在失配字符前有一個字符重復時，s串www.baidu與t串ww.在下標為3的位置失配時，按照第一種情況應(yīng)該把s[3]與t[1]匹配，匹配不成功，但卻會錯過它的正確匹配的位置，即s[2]與t[1]開始進行匹配后發(fā)現(xiàn)，s[2]=t[1]、s[3]=t[2]、s[4]與t[3]，模式串向右滑動了1個字符，找到模式串在主串中的起始位置為2.

第三種情況是t串在失配字符前有兩個字符重復時：s串a(chǎn)bsabsqueen和t串a(chǎn)bsabc在下標為6的位置失配時，下一個與s[6]要進行匹配的t串字符應(yīng)該是哪一個呢，通過觀察會發(fā)現(xiàn)在t串失配字符前有兩個字符是重復的，即t[1]= t[4]、t[2]= t[5]，而t[4]=s[4]、t[5]=s[5]，所以t[1]=s[4]、t[2]=s[5]，t[3]會不會和s[6]匹配，要經(jīng)過比較后才知道，所以不能放過任何一種可能性，應(yīng)該嘗試把重復部分的后一個字符與s[6]進行匹配，模式串t向右滑動了5個字符，減少了4次匹配次數(shù)。

第四種情況是t串在失配字符前所有的字符都相同時：對于特殊字符s串ssssanmx和t串ssssb，在失配的下標為5的位置的字符前的字符串有最長三個字符重復，正常情況下，仍然可以直接用T[4]號元素與s串失配的字符進行匹配，發(fā)現(xiàn)t[4]與s[5]仍然失配，且t[4]= t[3]= t[2]= t[1]，沒有必要讓t[3]、t[2]、t[1]都與s[5]匹配一次，直接將t[1]與是s[6]進行匹配，提高了效率。

從以上分析過程中不難發(fā)現(xiàn)為了求出第j個字符前最長長度相等的公共元素k，kmp算法引進了一個next函數(shù)[3]，next[j]即表示了t串中的第j個字符與主串s中相應(yīng)字符失配時，在模式串t中需要重新和主串s中該字符進行比較的字符位置。因此next函數(shù)的求解過程是kmp算法的關(guān)鍵，盡管next函數(shù)值可以用遞歸和next函數(shù)本身的定義出發(fā)對它進行計算，但其過程還是比較難理解，若加上其代碼的形成過程，更是讓眾多初學者感覺是懂非懂，因此本文對kmp算法提出了一點改進，對于k值，不用next函數(shù)對其進行求解，而是把k值的計算融入到算法中去，主觀上更容易理解其匹配過程，而代碼看起來也更簡潔易懂。

3 kmp算法的改進

改進的算法的過程如下：

（1）遵循kmp算法的指導思想，主串s與模式串t匹配時，當發(fā)生失配時，尋找下一個與s串失配字符匹配的t串字符時，主串s的下標i不回溯。

（2）主串字符s[i]與模式串字符t[j]匹配發(fā)生失配時，設(shè)置變量k使得主串s[k]，（i-j+2<=k

（3）若模式串t的下標j大于模式串的長度時則表示在主串中找到了模式串。

其改進的算法代碼如下：

輸入一個字符串s為主串;

輸入一個字符串t為模式串;

i=1;

j=1;

While （i<=len（s） && j<=len（t）） //len（s）為主串s長度，len（t）為模式串t的長度

{? ? if（s[i]=t[j]）

{i++;

j++

}

else

{ k=i-j+2;

j=1;

I++;

While （k

{if（s[k]==t[j]）

{K++;

j++;}

Else

{k++;

j=1;

}

}

}

}

4 改進算法可行性

取主串s為qvqbqvcbdw，模式串t為qvcbd時，當初始值都為1時s[1] =t[1]， i和j的值各加1，i=2，j=2，根據(jù)改進算法的程序，這樣循環(huán)比較直至s[3] ≠t[3]時，重新置j=1，k=i-j+2=2，i加1后i=4，這時k的值小于i且j的值小于t串的長度，將t[1]的值與s[k]即s[2]的值進行比較后t[1]≠s[2]，k值加1后k=2+1=3，j重新置1即j=1，這時k的值小于i且j的值小于t串的長度，將s[k]即s[3]與t[1]比較后s[3] =t[1]，k的值加1即k=3+1=4，j的值加1后j=2，這時k的值不小于i，條件不滿足，回到程序起始狀態(tài)，將t串第二個字符與s串的第四個字符比較，s[i]即s[4]的值與t[2]的值進行比較，但s[4] ≠t[2]，k的值為k=4-2+2=4， j重新置1即j=1，i的值加1后i=5，這時k的值小于i， 將s[k]即s[4]與t[1]進行比較，s[4] ≠t[1]，k值加1后k=4+1=5，j重新置1即j=1，這時k的值不小于i，條件不滿足，回到程序起始狀態(tài)比較s[5]與t[1]的值后s[5]=t[1]，i和j的值各加1，i=5，j=2，接著比較s[6]和t[2]的值依然相等，以此類推，直至比較到s[8]=t[5]后，j的值大于t串的長度，找到模式串在主串的起始位置為5，其比較次數(shù)如表 1所示：

以上例子對改進的算法進行了驗證，發(fā)現(xiàn)其能遵循i不回溯的原則，比較的次數(shù)與使用KMP算法的字符匹配的次數(shù)相同，模式串右移了盡可能最大的距離，且其時間復雜度為O（m+n），這樣的比較過程在直觀上更易于理解，且同樣能達到匹配字符串的效果。

參考文獻

[1].潘群娜.基于模式匹配KMP算法的探討[J].科技信息（科學教研），2007（13）：335+377.

[2].李莉，江育娥，林劼，等.基于KMP算法的改進算法KMPP[J].計算機工程與應(yīng)用，2016，52（8）：33-37.

[3].周雅翠，孫磊.基于KMP算法的next函數(shù)理解與分析[J].吉林建筑工程學院學報，2012，29（1）：79-82.

收稿日期：2020-03-23

作者簡介：姚秀情（1980—），女，福建閩清人，本科，實驗師，從事計算機基礎(chǔ)教學工作。

On the Improvement of KMP Algorithm

YAO Xiu-qing

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

Absrtact： This paper analyzes the formation process of pattern matching algorithm KMP with several different examples of whether pattern string t has repetition. It integrates the calculation of next function which is difficult to understand into the algorithm， and makes a little improvement on the algorithm. The improved algorithm follows the principle of no backtracking of main string pointer of KMP algorithm， but it is easier to understand.

Keywords： string matching; next array; algorithm improvement