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

摘要：在各類程序設(shè)計(jì)競賽中，字符串匹配相關(guān)的題目雖然并不常見，但掌握相關(guān)的算法卻是每個(gè)算法學(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算法，是一種在線性時(shí)間內(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)版本，即通過在時(shí)間復(fù)雜度為O（m）的時(shí)間內(nèi)生成一張前綴表（預(yù)處理）以省去計(jì)算轉(zhuǎn)移函數(shù)δ的時(shí)間。下面給出了字符串匹配問題的形式化定義。

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

字符串匹配問題的形式化定義如下：假設(shè)文本串是一個(gè)長度為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的每個(gè)元素pi，都存在一個(gè)實(shí)數(shù)k（k≥0），使得模式串pat開頭的前k個(gè)字符（p0， p1， … pk-1）依次與pi前面的k個(gè)字符（pi-k ， pi-k+1 ， … pi-1 ，這里的第一個(gè)字符pi-k最多從p1開始（即i-k≥1），且k<i+1（因?yàn)樽哟偣矁H有i+1個(gè)字符））相同。如果這樣的k有多個(gè)，則取最大的一個(gè)?？梢钥吹侥Ｊ酱畃at中每個(gè)位置為i的字符都有著這樣的k，在本文里采用next數(shù)組存儲。那么得出了 next[i]=max{k}。

如果直接根據(jù)next數(shù)組的定義求next數(shù)組，時(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è)字符所構(gòu)成的子串為prefix[i]，p[i]前面的next[i]個(gè)字符構(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ù)組的時(shí)間復(fù)雜度是Ο（m）。于是實(shí)現(xiàn)了以Ο（m+n）的時(shí)間復(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)把每一個(gè)next[i]看成一個(gè)狀態(tài)，構(gòu)建的過程可以看成模式串pat自己與自己的匹配，也就是狀態(tài)的轉(zhuǎn)移。

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

在現(xiàn)實(shí)生活中處處離不開字符串匹配的情景，比如文檔的查找功能或是關(guān)鍵字定位等等，研究相應(yīng)的算法對小組成員思維和競賽水平的鍛煉與提升有著巨大的幫助。KMP算法巧妙的思想不僅僅可以幫助解決字符串匹配相關(guān)的問題，更重要的在于其可以潛移默化地在解決其他問題時(shí)提供新的思路或參考方向。算法學(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)輸入的第一行包含一個(gè)整數(shù)n，表示有n組數(shù)據(jù)。

接下來的每兩行里第一行包含了一個(gè)字符串W {'A'， 'B'， 'C' … 'Z'}，下一行包含一個(gè)字符串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]），如不做此修改則會超時(shí)。

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

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

首先，把寶寶父母親的名字加起來拼湊成一個(gè)新的字符串S;接著，在S的所有公共前后綴子串里挑一個(gè)給寶寶起名。比如：父親的名字是“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”。現(xiàn)有一個(gè)字符串S，需要幫助法師編寫一個(gè)程序以計(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)在這最長的公共前后綴里了。只要按照這個(gè)思路一直循環(huán)下去直到next[i] = 0時(shí)就說明找到所有的公共前后綴。例如樣例一的ababcababababcabab，它的最長公共前后綴為ababcabab（即在next數(shù)組里next[18] = 9）。因?yàn)槠渌墓睬昂缶Y只會比“ababcabab”短，所以按動態(tài)規(guī)劃的思想一樣把眼光專注于這個(gè)子串，它的最長公共前后綴為next[9] = 4;依次循環(huán)，next[4] = 2;next[2] = 0（也就是子串“ab”已經(jīng)沒有公共前后綴了）。于是求出了所有的公共前后綴。它們的長度在計(jì)算保存一下即可。其主要代碼如圖3所示。

3）Power Strings問題[4]

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

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

輸出：對于每組輸入，對于滿足x = a*n的字符串中數(shù)量最多的那個(gè)字符串a(chǎn)，你需要給出有多少個(gè)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]

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

輸入：一個(gè)字符串s

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

樣例示范：

樣例1：

輸入：abcdabcd

輸出：true

樣例2：

輸入：abaabaaba

輸出：true

樣例3：

輸入：abababa

輸出：false

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

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

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

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

經(jīng)過上面的分析，合法的子串si（不一定最短）必定會組成s的前綴和后綴，涉及前綴子串和后綴子串，就不難想到之前說過的KMP算法了。在求next數(shù)組時(shí)，就需要求最長的相等前后綴。利用這個(gè)性質(zhì)，就可以快速來解一道題了。當(dāng)計(jì)算出KMP中的next數(shù)組的最長相等前后綴時(shí)，若存在k個(gè)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ù)組時(shí)讓點(diǎn)i的父親為next[i]。通過next數(shù)組把0 … n個(gè)點(diǎn)連成一棵樹。這種樹有性質(zhì)主要有：

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

2）任意兩個(gè)點(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)系的兩個(gè)點(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é)生。