KMP算法在程序設計競賽中的應用實踐探究

安梓堯 毛玉萃 秦偉勛 郭涵濤

摘要：在各類程序設計競賽中，字符串匹配相關的題目雖然并不常見，但掌握相關的算法卻是每個算法學習者必走的路程。介紹了KMP算法對實際生活和競賽的重要性;簡述了KMP算法的原理及其相關的一些算法題目。最后介紹了KMP算法思想在其他算法中的體現。

關鍵詞：KMP;程序類競賽;實例

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

文章編號：1009-3044（2022）14-0080-03

1 KMP算法簡述

KMP 算法全稱Knuth-Morris-Pratt算法，是一種在線性時間內解決字符串匹配問題的算法。在1977年由D.E.Knuth、J.H.Morris和V.R.Pratt三人聯合發表。在算法導論第32章里討論了4種字符串的匹配算法，分別是BF暴力匹配、Rabin-Karp算法、有限自動機和KMP算法[1]。其中KMP算法就可以說是有限自動機（DFA）的改進版本，即通過在時間復雜度為O（m）的時間內生成一張前綴表（預處理）以省去計算轉移函數δ的時間。下面給出了字符串匹配問題的形式化定義。

1）字符串匹配問題的形式化定義[1]

字符串匹配問題的形式化定義如下：假設文本串是一個長度為n的字符數組txt[1 … n]，模式串是欲與文本串進行匹配的字符數組pat[1 … m]，其中m≤n且m≠∞、n≠∞，而txt、pat的元素都來自有限字母集∑（即元素都是可打印可輸入的）。如果存在0≤s≤n-m且txt[1+s … m+s]=pat[1 … m]，那么稱模式串pat在文本串txt中以有效偏移s出現（即模式串是在文本串的第s+1到s+m位置處出現）。現需要找到所有的有效偏移s使得在該有效偏移下模式串出現在文本串的相應位置。

2）KMP算法的原理

對于每模式串pat的每個元素pi，都存在一個實數k（k≥0），使得模式串pat開頭的前k個字符（p0， p1， … pk-1）依次與pi前面的k個字符（pi-k ， pi-k+1 ， … pi-1 ，這里的第一個字符pi-k最多從p1開始（即i-k≥1），且k<i+1（因為子串總共僅有i+1個字符））相同。如果這樣的k有多個，則取最大的一個。可以看到模式串pat中每個位置為i的字符都有著這樣的k，在本文里采用next數組存儲。那么得出了 next[i]=max{k}。

如果直接根據next數組的定義求next數組，時間復雜度會有Ο（m2），并不是優秀的速度。其實相較于BF暴力匹配一次一次的迭代回溯，KMP算法就在于巧妙地運用了之前已匹配過的信息并加以運用。所以不妨這樣假設，若next[0]， next[1]， … next[i-1]均已知，根據p[i]的情況進行分類討論：

p[i] = p[next[i-1]]，也就是相等的最長前后綴的長度可以擴加一位。于是next[i] = next[i-1]+1;p[i] ≠ p[next[i-1]]，令子串p[0] … p[i]的前next[i]個字符所構成的子串為prefix[i]，p[i]前面的next[i]個字符構成的子串稱為suffix[i]，顯然地prefix[i]=suffix[i]。于是在滿足“p[0] … p[i-1]的next[i-1]前綴等于next[i-1]后綴”的條件下，可以知道子串p[0] … p[i]的prefix[i]一定落于prefix[i-1]中，suffix[i]一定落于suffix[i-1]中。因為prefix[i-1]=suffix[i-1]，所以所求的next[i]就是子串prefix[i-1]的相等的最長前后綴的長度，即next[i]=next[next[i-1]-1]。

進行攤還分析后可以證明此方法構建next數組的時間復雜度是Ο（m）。于是實現了以Ο（m+n）的時間復雜度構建next數組并利用next數組進行字符串匹配的算法。

如果對此方法進行進一步理解，可以發現構建next數組這一步所用的思想其實是動態規劃。當把每一個next[i]看成一個狀態，構建的過程可以看成模式串pat自己與自己的匹配，也就是狀態的轉移。

3）KMP算法的現實意義

在現實生活中處處離不開字符串匹配的情景，比如文檔的查找功能或是關鍵字定位等等，研究相應的算法對小組成員思維和競賽水平的鍛煉與提升有著巨大的幫助。KMP算法巧妙的思想不僅僅可以幫助解決字符串匹配相關的問題，更重要的在于其可以潛移默化地在解決其他問題時提供新的思路或參考方向。算法學習環環相扣，研究KMP算法有著莫大的意義。

4）KMP算法的競賽意義

各類程序設計競賽里考察字符串匹配的題目相比于其他算法題目并不是特別常見，但研究此類算法卻是小組成員學習其他字符串相關算法的必備條件之一。程序設計競賽對計算機相關專業的學生來說具有很大的幫助，考驗著學生的耐心、專注度、邏輯水平等。

5）KMP算法的C++代碼

KMP算法的用C++實現的代碼如圖1所示。

2 KMP算法在程序設計競賽中運用

1）Oulipo問題[2]

題目：求字符串W在字符串T中出現了幾次？

輸入：標準輸入的第一行包含一個整數n，表示有n組數據。

接下來的每兩行里第一行包含了一個字符串W {'A'， 'B'， 'C' … 'Z'}，下一行包含一個字符串T {'A'， 'B'， 'C' … 'Z'}

輸出： 對于每組測試樣例，輸出字符串W在字符串T中出現了幾次。

樣例輸入：

3

BAPC

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

樣例輸出：

1

3

0

分析：題目要求是求出W在T中出現的次數，很明顯，KMP就是解決這種問題的。圖2給出主要的算法代碼。需要注意的是第九行（j = next[j]），如不做此修改則會超時。

2）Seek the Name， Seek the Fame問題[3]

題目：有一位法師道法很強，人們總是為他們新出生的寶寶慕名而來，以求得法師為他們的孩子取吉利的名字。時間久了法師自然也就乏了，于是他想出了一個對策：

首先，把寶寶父母親的名字加起來拼湊成一個新的字符串S;接著，在S的所有公共前后綴子串里挑一個給寶寶起名。比如：父親的名字是“ala”， 母親的名字是“la”。 它們拼湊成的字符串S為“alala”。其中S的所有前綴為：“a”“al”“ala”“alal”“alala”;字符串S的所有后綴是：“a”“la”“ala”“lala”“alala”。所以它們的公共前后綴是：“a”“ala”“alala”。現有一個字符串S，需要幫助法師編寫一個程序以計算所有公共前后綴的長度。

輸入：輸入含有多組測試用例，每組用例均給出字符串S。注意字符串S只由小寫字母構成。

輸出：對于每組測試樣例，按從小到大輸出字符串S的所有公共前后綴的長度，代表著寶寶可能名字的長度。

樣例輸入：

ababcabab ababcabab

aaaaa

樣例輸出：

2 4 9 18

1 2 3 4 5

分析：要想得出公共前后綴的長度首先就需要求出字符串S的所有公共前后綴。這里就運用到了KMP中next數組的思想。具體地，因為next[i]數組的含義是p[1 … i]的最長公共前后綴，所以可以先求出字符串S的最長公共前后綴，那接下來的公共前后綴就只會出現在這最長的公共前后綴里了。只要按照這個思路一直循環下去直到next[i] = 0時就說明找到所有的公共前后綴。例如樣例一的ababcababababcabab，它的最長公共前后綴為ababcabab（即在next數組里next[18] = 9）。因為其他的公共前后綴只會比“ababcabab”短，所以按動態規劃的思想一樣把眼光專注于這個子串，它的最長公共前后綴為next[9] = 4;依次循環，next[4] = 2;next[2] = 0（也就是子串“ab”已經沒有公共前后綴了）。于是求出了所有的公共前后綴。它們的長度在計算保存一下即可。其主要代碼如圖3所示。

3）Power Strings問題[4]

題目：現有兩個字符串x， y，是這樣定義：x+y代表著將兩個字符串拼接在一起。比如，a=“abc”，b=“gcg”，那么a+b = “abcgcg”。同理[ i=0nxi]代表著n個字符串拼接在一起;n*x代表著n個相同的字符串x拼接在一起;0*x=“ ”代表著空字符串; （n+1） * x = x + x * n。

輸入：輸入多組測試用例，每組包含了一串可打印字符的字符串x（其長度為1-1000000）。最后一行為以“.”標識結束輸入。（本題有很大輸入，應使用scanf代替cin）

輸出：對于每組輸入，對于滿足x = a*n的字符串中數量最多的那個字符串a，你需要給出有多少個a拼接成了x。

樣例輸入：

abcd

aaaa

ababab

樣例輸出：

1

4

3

分析：在KMP算法中，next表示模式串pat的最長公共前后綴，也就是p[0] … p[next[i]]完全等于p[n-next[i]] … p[n]，所以若i%（i-next[i]） = 0，則可以說明存在著重復的連續子串，其長度為n-next[n]。其主要部分代碼如圖4所示。

4）重復的子字符串問題[5]

題目：給出一個長度大于0的字符串s，問這個字符串s是否能由若干個它的子串si來構成。

輸入：一個字符串s

輸出：若能由若干個子串構成則輸出true，否則輸出false

樣例示范：

樣例1：

輸入：abcdabcd

輸出：true

樣例2：

輸入：abaabaaba

輸出：true

樣例3：

輸入：abababa

輸出：false

解析：題目要求是找出一個s的子串si，來判斷能否由若干個si組成一個s。可以很容易地想到，如果可以從s中窮舉出可能出現的所有子串si，每當枚舉出一個si就使用這個si去不斷拼接自己，嘗試能否由k（k>1）個si組成一個s。

有了這個思路，可以計算一下時間復雜度。如果枚舉出一個字符串中的所有子串，是需要兩層for循環的，時間復雜度為O（n2）。有了枚舉出來的子串si就可以去進行拼接操作，進行k次拼接，得到一個與s長度相等的字符串，就可以進行字符串匹配比較了。拼接和比較相等的時間復雜度均為O（n）。

考慮優化不必要枚舉出所有的字符串，觀察樣例2，若枚舉出的一個子串是s.substr（3，3）。進行拼接時需要去把字符串s的前三位進行填充。若枚舉字符串只枚舉s.substr（1，i∈[0， s.length（））即可。枚舉時可以做進一步的優化的，假設枚舉的字符串si長度為si.length（），若s.length（）%si.length（）！=0則必定不能夠拼接出s。

設子串si為能夠拼出s的最短字符串，假設k個si能組成一個s。討論k的范圍，若k == 2，則兩個si分別一個組成s的前綴一個組成s的后綴。若k == 3，則可以由四個si平別組成s的前后綴，中間會重復一個si。若k == 4，則可以在k == 2的基礎上將兩個si合并成一個sj，組成了最終結果。k>= 4時以此類推。

經過上面的分析，合法的子串si（不一定最短）必定會組成s的前綴和后綴，涉及前綴子串和后綴子串，就不難想到之前說過的KMP算法了。在求next數組時，就需要求最長的相等前后綴。利用這個性質，就可以快速來解一道題了。當計算出KMP中的next數組的最長相等前后綴時，若存在k個si能組成s，則next[s.length（）-1]的值必定為s.length（）-si.length（）（其中si為滿足要求的最小子串長度）。 因而可以用s.length（）%si.length（） == 0來判斷是否存在符合題目要求的si。其實現的主要部分代碼如圖5所示。

3 KMP算法在其他算法中的運用

KMP算法還在許多其他算法中得以應用，在這里簡單介紹在 Border樹中的應用。

Boeder樹也叫作失配樹，就是運用KMP算法求失配數組時讓點i的父親為next[i]。通過next數組把0 … n個點連成一棵樹。這種樹有性質主要有：

1）每一個點的所有祖先一定是它自身的border。

2）任意兩個點的任意公共祖先是它們的共同的border。

3）傳遞性，若串a是串b的border，串b是串c的border，那么串a是串c的border。例如“aba”是“ababa”的border，“ababa”是“ababababa”的border。依據傳遞性，“aba”是“ababababa”沒有祖先關系的兩個點i，j沒有border。

4）借助Border樹的這些性質，可以衍生出各種應用，例如：求公共前綴串，和border的數量等。

4 結束語

算法的研究與學習總是沒有盡頭的，對KMP算法本質的理解同樣如此。在開展研究的過程中，作者彼此間互相提供豐富的建議與思路。作者非常期望這一簡單但很有意義的工作可以激發本領域更多同行研究人員在本方向上開展更為詳盡深入的研究。

參考文獻：

[1] Cormen T H.算法導論[M].殷建平，譯.北京：機械工業出版社，2013.

[2] Oulipo[EB/OL].[ 2021-10-14].http：//poj.org/problem？id=3461.

[3] Seek the Name， Seek the Fame[EB/OL].[2021-11-20].http：//poj.org/problem？id=2752.

[4] Power Strings[EB/OL].[2022-01-20].http：//poj.org/problem？id=2406.

[5] 重復的子字符串[EB/OL].[2021-10-22].https：//leetcode-cn.com/problems/repeated-substring-pattern/.

收稿日期：2022-02-16

基金項目：大連大學大學生創新創業訓練計劃項目：程序設計類競賽中KMP算法處理問題的研究與應用（項目編號：S202111258025）

作者簡介：安梓堯（2000—），男，云南紅河人，本科在讀;毛玉萃（1964—），女，江西高安人，副教授，碩士，研究方向為信息系統、算法和操作系統;秦偉勛（2001—），男，廣西桂林人，本科在讀;郭涵濤（2002—），男，山西永濟人，本科在讀學生。