KMP算法在程序設(shè)計(jì)競賽中的應(yīng)用實(shí)踐探究

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

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

關(guān)鍵詞：KMP;程序類競賽;實(shí)例

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

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

1 KMP算法簡述

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

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

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

2）KMP算法的原理

對于每模式串pat的每個元素pi，都存在一個實(shí)數(shù)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（因?yàn)樽哟偣矁H有i+1個字符））相同。如果這樣的k有多個，則取最大的一個。可以看到模式串pat中每個位置為i的字符都有著這樣的k，在本文里采用next數(shù)組存儲。那么得出了 next[i]=max{k}。

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

p[i] = p[next[i-1]]，也就是相等的最長前后綴的長度可以擴(kuò)加一位。于是next[i] = next[i-1]+1;p[i] ≠ p[next[i-1]]，令子串p[0] … p[i]的前next[i]個字符所構(gòu)成的子串為prefix[i]，p[i]前面的next[i]個字符構(gòu)成的子串稱為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]中。因?yàn)閜refix[i-1]=suffix[i-1]，所以所求的next[i]就是子串prefix[i-1]的相等的最長前后綴的長度，即next[i]=next[next[i-1]-1]。

進(jìn)行攤還分析后可以證明此方法構(gòu)建next數(shù)組的時間復(fù)雜度是Ο（m）。于是實(shí)現(xiàn)了以Ο（m+n）的時間復(fù)雜度構(gòu)建next數(shù)組并利用next數(shù)組進(jìn)行字符串匹配的算法。

如果對此方法進(jìn)行進(jìn)一步理解，可以發(fā)現(xiàn)構(gòu)建next數(shù)組這一步所用的思想其實(shí)是動態(tài)規(guī)劃。當(dāng)把每一個next[i]看成一個狀態(tài)，構(gòu)建的過程可以看成模式串pat自己與自己的匹配，也就是狀態(tài)的轉(zhuǎn)移。

3）KMP算法的現(xiàn)實(shí)意義

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

4）KMP算法的競賽意義

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

5）KMP算法的C++代碼

KMP算法的用C++實(shí)現(xiàn)的代碼如圖1所示。

2 KMP算法在程序設(shè)計(jì)競賽中運(yùn)用

1）Oulipo問題[2]

題目：求字符串W在字符串T中出現(xiàn)了幾次？

輸入：標(biāo)準(zhǔn)輸入的第一行包含一個整數(shù)n，表示有n組數(shù)據(jù)。

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

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

樣例輸入：

3

BAPC

BAPC

AZA

AZAZAZA

VERDI

AVERDXIVYERDIAN

樣例輸出：

1

3

0

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

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

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

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

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

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

樣例輸入：

ababcabab ababcabab

aaaaa

樣例輸出：

2 4 9 18

1 2 3 4 5

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

3）Power Strings問題[4]

題目：現(xiàn)有兩個字符串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）。最后一行為以“.”標(biāo)識結(jié)束輸入。（本題有很大輸入，應(yīng)使用scanf代替cin）

輸出：對于每組輸入，對于滿足x = a*n的字符串中數(shù)量最多的那個字符串a(chǎn)，你需要給出有多少個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，則可以說明存在著重復(fù)的連續(xù)子串，其長度為n-next[n]。其主要部分代碼如圖4所示。

4）重復(fù)的子字符串問題[5]

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

輸入：一個字符串s

輸出：若能由若干個子串構(gòu)成則輸出true，否則輸出false

樣例示范：

樣例1：

輸入：abcdabcd

輸出：true

樣例2：

輸入：abaabaaba

輸出：true

樣例3：

輸入：abababa

輸出：false

解析：題目要求是找出一個s的子串si，來判斷能否由若干個si組成一個s?？梢院苋菀椎叵氲剑绻梢詮膕中窮舉出可能出現(xiàn)的所有子串si，每當(dāng)枚舉出一個si就使用這個si去不斷拼接自己，嘗試能否由k（k>1）個si組成一個s。

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

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

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

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

3 KMP算法在其他算法中的運(yùn)用

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

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

1）每一個點(diǎn)的所有祖先一定是它自身的border。

2）任意兩個點(diǎn)的任意公共祖先是它們的共同的border。

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

[1] Cormen T H.算法導(dǎo)論[M].殷建平，譯.北京：機(jī)械工業(yè)出版社，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] 重復(fù)的子字符串[EB/OL].[2021-10-22].https：//leetcode-cn.com/problems/repeated-substring-pattern/.

收稿日期：2022-02-16

基金項(xiàng)目：大連大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目：程序設(shè)計(jì)類競賽中KMP算法處理問題的研究與應(yīng)用（項(xiàng)目編號：S202111258025）

作者簡介：安梓堯（2000—），男，云南紅河人，本科在讀;毛玉萃（1964—），女，江西高安人，副教授，碩士，研究方向?yàn)樾畔⑾到y(tǒng)、算法和操作系統(tǒng);秦偉勛（2001—），男，廣西桂林人，本科在讀;郭涵濤（2002—），男，山西永濟(jì)人，本科在讀學(xué)生。