最長(zhǎng)重復(fù)子串

1、最長(zhǎng)重復(fù)子串最長(zhǎng)重復(fù)子串湖南長(zhǎng)沙市雅禮中學(xué)湖南長(zhǎng)沙市雅禮中學(xué)龍凡龍凡【關(guān)鍵詞關(guān)鍵詞】擴(kuò)展擴(kuò)展KMPKMP算法算法二分二分后綴數(shù)組后綴數(shù)組后綴樹(shù)后綴樹(shù)【引言引言】近些年來(lái)，字符串類型的試題越來(lái)越多的出現(xiàn)在信息學(xué)競(jìng)賽中。而字符串處理中常常出現(xiàn)的一類問(wèn)題即——最長(zhǎng)重復(fù)子串。本文將討論最長(zhǎng)重復(fù)子串問(wèn)題及它的幾種變形，并給出實(shí)際應(yīng)用中效果較好的解決該類問(wèn)題的幾種方法。文中將涉及到使用擴(kuò)展KMP、后綴數(shù)組等工具性算法。這些算法的具體方法與實(shí)現(xiàn)請(qǐng)參考

2、近年來(lái)的國(guó)家集訓(xùn)隊(duì)論文?！具B續(xù)最長(zhǎng)重復(fù)子串連續(xù)最長(zhǎng)重復(fù)子串】1.問(wèn)題描述給定一個(gè)長(zhǎng)度為N的字符串S。記為S的第I個(gè)字符到第J個(gè)字)(jis)(nji??符所組成的子串。若存在，則稱S存在一個(gè)長(zhǎng)度為K的)12()1(??????kikiskiis連續(xù)重復(fù)子串?，F(xiàn)在要你求出K的最大值，滿足存在一個(gè)值I使得。)12()1(??????kIkiskiis2.基于二分的算法枚舉K，然后掃描的方法的時(shí)間復(fù)雜度高達(dá)O(N2)，效果并不能讓人滿意。我們

3、需要更高效的算法，這里給出一個(gè)基于二分結(jié)合擴(kuò)展KMP算法的算法，時(shí)間復(fù)雜度為O(Nlog2N)。在介紹主算法之前，我們先來(lái)簡(jiǎn)要介紹擴(kuò)展KMP算法，這里并不對(duì)擴(kuò)展KMP算法具體如何實(shí)現(xiàn)進(jìn)行介紹，僅僅為了方便讀者理解，介紹擴(kuò)展KMP算法的功能。具體的擴(kuò)展KMP算法的實(shí)現(xiàn)，請(qǐng)參考2003年國(guó)家集訓(xùn)隊(duì)林希德的論文。擴(kuò)展KMP算法：對(duì)于一個(gè)主串S，和一個(gè)模式串T。記。而擴(kuò)展KMP算法可以在O(Len(S)Len(T))時(shí)間復(fù)雜)1()1(max)

4、(ktkiiskiq????度內(nèi)求解q(1)…q(len(s))。現(xiàn)在回到主算法，對(duì)于一個(gè)給定的串S。設(shè)Ans(S)為該串的連續(xù)最長(zhǎng)重復(fù)子串長(zhǎng)度。那么可以知道：)())1(())((max))((rlCrossrsAnslsAnsrlsAns??其中Cross(lr)表示：在s(lr)中，包含s()和s(1)這兩個(gè)字符的連續(xù)最長(zhǎng)重復(fù)子串長(zhǎng)度。根據(jù)上面的性質(zhì)，我們二分求解Ans(S(lr))，令。如????????2rl兩種情況的時(shí)間復(fù)雜

5、度為O(rl)。那么如何預(yù)先算出West數(shù)組和East數(shù)組呢？通過(guò)分析我們發(fā)現(xiàn)：設(shè)Rotate(S)表示S字符串的逆字符串：比如Rotate(‘123’)=Rotate(‘321’)。則West數(shù)組事實(shí)上是Rotate(s(lr))作為母串，Rotate(s(l))作為模式串時(shí)，擴(kuò)展KMP算法求得的Q數(shù)組。而East數(shù)組則是S(lr)作為母串，s(1r)作為模式串時(shí)，擴(kuò)展KMP算法求得的Q數(shù)組。我們只要預(yù)先執(zhí)行兩次擴(kuò)展KMP算法，就能在

6、O(rl)的時(shí)間復(fù)雜度內(nèi)求得West數(shù)組和East數(shù)組。那么我們計(jì)算Css(lr)的時(shí)間復(fù)雜度也為O(rl)，也就是說(shuō)我們可以利用二分配合擴(kuò)展KMP算法在O(Nlog2N)的時(shí)間復(fù)雜度內(nèi)求得Ans(S(1n))，即我們要求的答案。3.其他解決方法上面，我們給出了O(Nlog2N)的時(shí)間復(fù)雜度內(nèi)利用二分＋擴(kuò)展KMP求解連續(xù)最長(zhǎng)重復(fù)子串的算法。事實(shí)上，這道題目利用后綴樹(shù)配合擴(kuò)展KMP，可以在O(NLog2Σ)的時(shí)間復(fù)雜度內(nèi)解決（其中Σ是字符

7、串涉及的字符集大?。?。由于后綴樹(shù)實(shí)現(xiàn)較為復(fù)雜，并且對(duì)空間要求較高，這里就不作介紹了。有興趣的讀者可以參考2003年國(guó)家集訓(xùn)隊(duì)員林希德的論文?！具B續(xù)重復(fù)子串的擴(kuò)展連續(xù)重復(fù)子串的擴(kuò)展】1問(wèn)題的擴(kuò)展給出一個(gè)長(zhǎng)度為N的字符串S以及整數(shù)g。有多少對(duì)不同的i、j使得：，且。)12()1(????????gkigkiSkiiS112?????kjgki題目來(lái)源：UVA10829LGapSubstring，原題1050000??gN2算法分析這道題目相

8、比經(jīng)典的連續(xù)最長(zhǎng)重復(fù)子串問(wèn)題，有兩點(diǎn)不同：1.題目中有一個(gè)g的參量，這個(gè)參量的意義相當(dāng)于兩個(gè)重復(fù)子串之間的間隔長(zhǎng)度。當(dāng)g=0時(shí)即連續(xù)重復(fù)子串。2.題目需要我們給出的是長(zhǎng)度大于1的重復(fù)子串的個(gè)數(shù)，而不是最長(zhǎng)重復(fù)子串的長(zhǎng)度。我們?nèi)匀粐L試使用二分配合擴(kuò)展KMP算法的方法來(lái)求解該問(wèn)題。設(shè)Ans(s)為字符串為字符串S滿足題目條件的重復(fù)子串個(gè)數(shù)滿足題目條件的重復(fù)子串個(gè)數(shù)。和連續(xù)重復(fù)子串經(jīng)典問(wèn)題一樣，我們有：)())1(())(())((rlCro