求最大重復(fù)子串

1、求最大重復(fù)子串 1題目 字符串W由大寫字母組成，W中包含一些連續(xù)出現(xiàn)兩次的相同子串，稱之為重復(fù)子串。重復(fù)子串的大小決定于循環(huán)節(jié)的長度。2W =“B B A A B A B A A B A B B”A B A A B A舉例B B循環(huán)節(jié)長度為3循環(huán)節(jié)長度為13 請你求出最大重復(fù)子串的循環(huán)節(jié)長度。題目 字符串W由大寫字母組成，W中包含一些連續(xù)出現(xiàn)兩次的相同子串，稱之為重復(fù)子串。重復(fù)子串的大小決定于循環(huán)節(jié)的長度。4數(shù)據(jù)規(guī)模n = |w| = 100000O(n2)O(nlg2n)O(n)5后綴樹兩個輔助算法O(n) KMP模式匹配O(n+m)為方便表達(dá)，使用表示開始于位置u結(jié)束于位置v的W的子串W

2、( u ，v )6問題的轉(zhuǎn)化1、S中的字符以L為周期循環(huán)出現(xiàn) S i = S i + L （u = i = 2 L，即S至少包括兩個完整循環(huán)節(jié)。3、S不能向左擴(kuò)展， 即u = 1 或者 W(u-1,v)不滿足條件14、S不能向右擴(kuò)展， 即 v = n 或者 W(u,v+1)不滿足條件1最大重復(fù)子串必然被某個最優(yōu)子串包含！7算法基本框架1、找到S的一個完整循環(huán)節(jié) 2、根據(jù)循環(huán)節(jié)將S分別向左、向右擴(kuò)展到不能擴(kuò)展為止 3、判斷擴(kuò)展以后的S是否長度 = 2 L 如果是，則認(rèn)為找到了一個循環(huán)周期為L的最優(yōu)子串S。?8如果字母Q1從未在P中出現(xiàn)過, 那么 Ui = Q1 否則 Ui = P中出現(xiàn)過的Q的最

3、長前綴一、字符串分解Ui-1PQUi-2U1字符串W 將W分解成 W = U1 + U2 + U3 + + Um 的形式，其中Ui定義如下： W = P + Q P = U1 + U2 + + Ui-1 Q1只要字符串x的開始位置在P內(nèi)，就認(rèn)為x在P中出現(xiàn)過！9A B A A B A B A A B A B B 舉例PQA10A B A A B A B A A B A A B 舉例PQB11A B A A B A B A A B A A B 舉例PQAA12A B A A B A B A A B A A B 舉例PQA B AA B A13A B A A B A B A A B A A B 舉

4、例PQB A A B AB A A B A14A B A A B A B A A B A A B 舉例PQ15A B A A B A B A A B A A B 舉例字符串分解過程借助“后綴樹”算法實(shí)現(xiàn)A B A B16 怎樣利用字符串分解的特殊定義找到最優(yōu)子串S的一個完整循環(huán)節(jié)呢？ S的循環(huán)節(jié)能有多長呢?分類討論。二、尋找完整循環(huán)節(jié)問題： S的開始位置在何處呢？ 解決方法： 假設(shè)S的結(jié)束位置在固定片斷Ui內(nèi)一定要記住：整數(shù)i是個已知常量！17S的開始位置也在Ui內(nèi). Ui在P中某處出現(xiàn)過 S在P中某處出現(xiàn)過為避免重復(fù)工作，此情況不予考慮！最優(yōu)子串SUiPQS的開始位置不能太遲這里用到了字符串

5、分解的定義18最優(yōu)子串Sb. 最末循環(huán)節(jié)包含Ui-1UiUi-1PQ最末循環(huán)節(jié)紅色和綠色線段標(biāo)示了相同的子串根據(jù)定義，|Ui-1| = 紅色線段矛盾，情況b不存在。S的循環(huán)節(jié)不能太長這里再次用到了字符串分解的定義Ui-119最優(yōu)子串Sc. |S位于Ui-1之前的子串| = 循環(huán)周期LUiUi-1PQ最末循環(huán)周期紅色和綠色線段標(biāo)示了相同子串根據(jù)定義，|Ui-1| = 紅色線段矛盾，情況c也不存在。S的開始位置不能太早這里又一次用到了字符串分解的定義20重要結(jié)論11. S的開始位置早于Ui且最末循環(huán)節(jié)沒有將Ui-1包含在內(nèi)，故L |Ui-1 + Ui|2. |S位于Ui-1之前的子串| 循環(huán)周期L

6、，故|S| = 2，故下列兩種情況S必居其一： 情況1. S在V中的長度 = L 情況2. S在U中的長度 = L 最優(yōu)子串SUi實(shí)際就是的一個完整循環(huán)節(jié)U(1,L)這個結(jié)論很重要！找到循環(huán)節(jié)了!22VU最優(yōu)子串S 1、盡量向右擴(kuò)展 三、循環(huán)節(jié)擴(kuò)展和長度判定完整循環(huán)節(jié) 2、盡量向左擴(kuò)展 3、如果擴(kuò)展以后的|S| = 2L，那么 S是最優(yōu)子串。U(1,L)實(shí)際就是的一個完整循環(huán)節(jié)找到循環(huán)節(jié)了!23B B A A B A B A A B A B B 舉例VU尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)24舉例B B A A B A B A A B A B B VU尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)25舉

7、例B B A A B A B A A B A B B VU尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)26舉例B B A A B A B A A B A B B VU結(jié)束位置尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)27舉例B B A A B A B A A B A B B VU尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)結(jié)束位置28舉例B B A A B A B A A B A B B VU尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)結(jié)束位置29舉例B B A A B A B A A B A B B VU尋找循環(huán)周期為5的最優(yōu)子串完整循環(huán)節(jié)結(jié)束位置30舉例B B A A B A B A A B A B B VU尋找循環(huán)周

8、期為5的最優(yōu)子串完整循環(huán)節(jié)結(jié)束位置31舉例B B A A B A B A A B A B B VU開始位置長度判定：|S| = 11 = 2 * 5尋找循環(huán)周期為5的最優(yōu)子串結(jié)束位置S是合法最優(yōu)子串完整循環(huán)節(jié)32VU完整循環(huán)節(jié)輔助函數(shù)和重要結(jié)論2B B A A B A B A A B A B B LsL = U 與U(1+L，|U|)的最長公共前綴 LpL = V 與V + U(1，L)的最長公共后綴 當(dāng)且僅當(dāng)|LsL + LpL| = L時 存在唯一的周期為L的最優(yōu)子串 LsL + U(1,L) + LpL A B向右擴(kuò)展B A A B向左擴(kuò)展長度判定B A A BA B長度判定：|S| =

9、 11 = 2 * 5S是合法最優(yōu)子串33 使用一次“KMP模式匹配的推廣算法”在線性時間內(nèi)求出所有Lp和Ls的函數(shù)值 四、枚舉所有最優(yōu)子串因?yàn)椋篖s函數(shù)定義中，第一個有待比較前綴的字符串總是U Lp函數(shù)定義中，第一個有待比較后綴的字符串總是V所以：我們可以然后：從 1 到 |Ui + Ui-1| 枚舉循環(huán)節(jié)的長度L， 并在枚舉的同時判斷是否 |LsL + LpL| = L，即可： 找出所有最優(yōu)子串連同它們的周期。這樣Lp和Ls函數(shù)的平攤求解復(fù)雜度為O(1) LsL = 與U(1+L，|U|)的最長公共前綴 LpL = 與V + U(1，L)的最長公共后綴 U V 34算法基本框架回顧和完善字符串分解answer = 0 令 V = 長度為 |Ui| + 2 * |Ui-1|的P的后綴 U = Ui For i = 2 to m do End For 針對情況1：S在V中的長度 = L End 情況1 1、 求出函數(shù)Ls和函數(shù)Lp的值 針對情況2：S在U中的長度 = L End 情況2 2、 For L=1 to |Ui-1 + Ui|-1 do 輸出 answer If |LsL| + |LpL| = L Then 用L更新answer的值 35算法性能分析 較大 20