1、擴(kuò)展KMP算法湖南 周戈林1內(nèi)容介紹串匹配問題是一類實(shí)用價(jià)值很高的信息學(xué)問題。對于這類問題，我們一般使用功能強(qiáng)大的后綴樹和后綴數(shù)組加以解決。傳統(tǒng)的KMP算法由于功能簡單，往往不受重視。但值得注意的是，后綴樹和后綴數(shù)組的編程復(fù)雜度很高，程序運(yùn)行常數(shù)極大，空間耗費(fèi)也不小，在解決數(shù)據(jù)范圍很大的問題時(shí)顯得力不從心。在某些情況下，運(yùn)用KMP算法的改進(jìn)，也就是擴(kuò)展KMP算法可以恰到好處地解決問題。2主算法給定一個(gè)串S，定義n=|S|，extendi表示S與Sin的最長公共前綴長度。我們可以在線性時(shí)間內(nèi)得到所有的extendi。鑒于已有論文對這個(gè)算法進(jìn)行細(xì)致、感性的描述，在此就不花費(fèi)篇幅贅述這一算法。如果您

2、想詳細(xì)了解這一算法，可以參見尋找最大重復(fù)子串（作者林希德）和求最長回文子串與最長重復(fù)子串（作者何林）。3算法的應(yīng)用例一：模板Byteasar想用一條相當(dāng)長的圖案（內(nèi)容是一個(gè)字符串）裝飾他的屋子。為了這個(gè)，他必須準(zhǔn)備一個(gè)適當(dāng)?shù)哪０?，這個(gè)模板跟圖案的前一段相同。他將會把模板放在墻壁的某些位置，然后按照模板進(jìn)行描繪。他每次只能描繪當(dāng)時(shí)模板覆蓋到的所有位置，不能只描繪其中的一些。同時(shí)只要字母符合，墻壁的每個(gè)位置都可以被描繪多次。模板上所有的字母都是相鄰的，其中沒有空格。當(dāng)然，我們總是能找到一個(gè)模板能拼出整個(gè)圖案。但是Bytesar希望模板花費(fèi)最小，也就是這個(gè)模板盡量短。 任務(wù) 寫一個(gè)程序：從標(biāo)準(zhǔn)輸入中

3、讀入Byteasar想要描繪在墻壁上的圖案， 計(jì)算出完全描繪這個(gè)圖案所需的模板的最短長度，把結(jié)果寫到標(biāo)準(zhǔn)輸出中。 輸入描述 標(biāo)準(zhǔn)輸入僅包含一行，就是Byteasar想描繪在墻壁上的圖案，它包含最多500,000個(gè)英文小寫字母。輸出描述標(biāo)準(zhǔn)輸出僅包含一行，就是最短模板長度。樣例對于以下的輸入數(shù)據(jù)：ababbababbabababbabababbababbaba正確的輸出應(yīng)該是：8樣例的結(jié)果是這么來的：ababbababbabababbabababbababbabaababbaba ababbaba ababbaba ababbaba ababbaba解法分析本題要求找一個(gè)最短的模板串，把主串拼出

4、來。那么怎么樣的模板串才能拼出主串呢？首先，這個(gè)模板串既是主串的前綴，也是主串的后綴。因?yàn)闊o論怎么拼，總要拼主串的第一個(gè)和最后一個(gè)字符，而且不能多拼字符，所以模板串肯定要跟主串的前一段和后一段相等。其次，模板串要能覆蓋整個(gè)主串，也就是說每次描繪到的位置的并必須是整個(gè)主串。以上兩點(diǎn)性質(zhì)雖然十分簡單，但這為解題指明了方向：第一點(diǎn)確定了模板串的選擇范圍，第二點(diǎn)確定了判定一個(gè)模板是否合法的方法。我們定義主串為S,n=|S|，那么模板串T=S1m,1mn，我們希望m最小。顯然有以下算法：從小到大依次枚舉模板串的長度m，求出T=S1m在S中所有能匹配到的位置，從左到右依次記為p1, p2 ,pk ，顯然p

5、1=1。如果對于任意的1ik-1都有pi+1-pim，那么這就是一個(gè)合法的模板串，輸出它的長度再退出即可。這個(gè)算法很簡潔，唯一但是致命的缺點(diǎn)就是復(fù)雜度太高。即使用效率很高的KMP算法來尋找匹配位置，對于每個(gè)被枚舉的m也需要O(n)的時(shí)間來判斷是否可行?？倧?fù)雜度高達(dá)O(n2)，完全不具有可行性。我們研究一下樸素算法的細(xì)節(jié)，考察一下模板串的長度變大會導(dǎo)致什么變化。定理1當(dāng)m從m0變?yōu)閙0+1時(shí)，某些匹配點(diǎn)可能會消失，但是絕對不會出現(xiàn)新的匹配點(diǎn)。證明因?yàn)槊}的前一部分有“可能”這個(gè)詞，所以我們只需要證明不會出現(xiàn)新的匹配點(diǎn)。而這一點(diǎn)的證明十分簡單：如果新出現(xiàn)了某個(gè)匹配點(diǎn)q，那么就有S1m0+1=Sqq

6、+m0，顯然也有S1m0=Sqq+m0-1，也就說q在以前就是一個(gè)匹配點(diǎn)，與假設(shè)矛盾。定理1說明隨著m的增大，的值是單調(diào)不減的，而m的值在不斷增加，如果在某一時(shí)刻有l(wèi)m且pk=n-m+1就得到了最優(yōu)解?，F(xiàn)在我們的問題就是怎么在枚舉m的過程中維護(hù)l。這時(shí)就可以用到上文提到的擴(kuò)展KMP算法。首先預(yù)處理算出所有的extendi。當(dāng)枚舉的mextendi時(shí)，i就是一個(gè)匹配點(diǎn)。開始時(shí)我們把所有的i，也就是m=0時(shí)的匹配點(diǎn)存儲到一個(gè)雙向鏈表中，這樣刪除一個(gè)匹配點(diǎn)和更新l的值只需要O(1)時(shí)間。爾后，我們從小到大枚舉m，在枚舉的同時(shí)刪除不合要求的匹配點(diǎn)，當(dāng)?shù)谝粋€(gè)滿足要求的m出現(xiàn)時(shí)算法停止。假設(shè)當(dāng)前枚舉m到m

7、0，就把extendi=m0-1的i從鏈表中刪去，可以用哈希表輔助這一步。預(yù)處理的復(fù)雜度是O(n)的，同時(shí)每個(gè)位置只需要進(jìn)一次鏈表、出一次鏈表，而鏈表維護(hù)的費(fèi)用是O(1)，因此整個(gè)算法的時(shí)間復(fù)雜度就是線性的，是一個(gè)非常優(yōu)秀的算法。例二：單詞的周期一個(gè)串被定義為一個(gè)有限的英文小寫字母序列。特別的，這個(gè)序列可以為空，也就是說不包含任何字母。我們定義A=BC表示串A可以通過連接（把一個(gè)串接在另一個(gè)串的后面，也就是沒有空格隔開）串B和串C得到（按照這種順序）。如果存在兩個(gè)串P和B把它們連接之后能得到串A，也就是A=PB，我們就稱P是A的前綴。換句話說，A的前綴就是串A最前面的片斷。附加的，如果PA并且

8、串P不為空，我們就說P是A的嚴(yán)格前綴。 我們說串Q是串A的一個(gè)周期，僅當(dāng)Q是串A的嚴(yán)格前綴，并且串A是串QQ的前綴（不一定是嚴(yán)格前綴）。舉例來說，串a(chǎn)bab和ababab都是串a(chǎn)bababa的周期。串A的最長周期是它的周期中最長的一個(gè)，也有可能是空串，如果A沒有任何周期。舉例來說，串a(chǎn)babab的最長周期是abab。串a(chǎn)bc的最長周期是空串。 任務(wù) 寫一個(gè)程序：從標(biāo)準(zhǔn)輸入內(nèi)讀入一個(gè)串的長度以及這個(gè)串，統(tǒng)計(jì)這個(gè)串的所有前綴的最長周期長度和，把結(jié)果寫到標(biāo)準(zhǔn)輸出中。輸入描述 標(biāo)準(zhǔn)輸入第一行是一個(gè)整數(shù)n（1n1,000,000）串的長度。接下來一行有一個(gè)包含n個(gè)英文小寫字母的序列串的內(nèi)容。 輸出描述

9、標(biāo)準(zhǔn)輸出僅包含一行，就是標(biāo)準(zhǔn)輸入中串的所有前綴的最長周期長度和。樣例對于以下的輸入數(shù)據(jù)：8babababa正確的輸出應(yīng)該是：24樣例的結(jié)果是這么來的：b 最長周期為0ba 最長周期為0bab 最長周期為2baba 最長周期為2babab 最長周期為4bababa 最長周期為4bababab 最長周期為6babababa 最長周期為6 解法分析 把主串稱作串A，且n=|A|。我們跳過串的周期的定義，直接定義串的最長周期，這需要借助extend函數(shù)。我們先預(yù)定義f i=i+extendi+1。定理2若串A1m存在周期，那么它的最長周期就是Q=A1k，其中km-1, f km并且k的值盡量大。證明定

10、理2中的最長周期一定是串A的嚴(yán)格前綴，所以只需證明串A是串QQ的前綴，我們使用反證法證明。如果串A不是串QQ的前綴，那么只有兩種可能的情況：1|A|QQ|且A1mQQ1m；2|A|QQ|。由于fkm，因此有Q1m-k=Ak+1m，又Q=A1k，所以有QQ1m=A1m。這說明情況1不可能出現(xiàn)。假設(shè)情況2出現(xiàn)，由對情況1的分析知必有A1.2k=QQ。因?yàn)閒 km，所以A1.m-k=Ak+1m，也就有A1k=Ak+12k=A(p-1)k+1pk，此外還有Apk+1m=A1m-pk，其中。以上等式可用圖1表示：圖 SEQ 圖表 * ARABIC 1由以上討論知f pkm，這與k的最優(yōu)性不符，所以情況2

11、也不可能出現(xiàn)。在否定了兩種情況后，定理2的正確性就是顯然的了。直接應(yīng)用定理2就可以得到以下算法：對于每個(gè)m，從大到小枚舉對應(yīng)的k，直到找到一個(gè)滿足f km的k后停止，把這時(shí)的k值累加。這個(gè)算法在預(yù)處理之后需要兩重循環(huán)枚舉m和k，在最壞情況下的復(fù)雜度是O(n2)，太高了。注意到以下事實(shí)：假設(shè)我們從小大到大枚舉m，恰好枚舉到m=m0，又存在ijm0且f if j，那么A1i在這之后肯定不會成為某個(gè)A1m,mm0的最長周期。這是因?yàn)楫?dāng)i和j都是周期時(shí)j比i更優(yōu)，而當(dāng)j不是周期的時(shí)候i也一定不是周期。我們可以維護(hù)一個(gè)棧k1, k2, k3, kp記錄當(dāng)前有可能成為最長周期的位置，它們滿足，以及。假設(shè)我們處理到A1i：就先判斷f kp與f i-1的大小關(guān)系，如果f kpf i-1就將棧頂元素出棧，直到f kpf i-1為止，再把i-1入棧。此后再將判斷f kp與i的大小關(guān)系，如果f kpi就將棧頂元素出棧，直到f kpi或者棧空為止。這時(shí)如果棧空說明A1i沒有周期，否則其最長周期為A1kp。每個(gè)位置最多進(jìn)一次棧出一次棧，所以對棧的維護(hù)總共需要O(n)的時(shí)間。本題的時(shí)間復(fù)雜度就是O(n)。4總結(jié)在本文所述的兩道例題的解答過程中，我們跳出了一般的思維慣性，避開了繁瑣的高級數(shù)據(jù)結(jié)構(gòu)，同時(shí)盡可能地將題目條件與extend函數(shù)建立關(guān)系，從而使得可以用擴(kuò)展KMP來解題。但僅僅這樣是不足