TA的每日心情 | 哭哭 2015-5-8 16:37 |
---|
簽到天數: 13 天 [LV.3]偶爾看看II
高一新生
- 積分
- 101
|
趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
各位學弟妹:
很抱歉因為我一直忘記所以這篇文到現在才發 Orz
寒訊時我們在講字串時有討論到一個題目如下:
給定一個字串 S,求最長的子串 T 滿足 TT 是 S 的子串。
當時我沒有給出一個好的作法,事實上原因是我記錯題目了 XD
我當時看到的題目應該是類似 T 不需要連續出現,或者是求出連續出現次數最多的子串之類的。
至於這個巧妙的錯誤,事實上是一個並不簡單的問題,目前人類已知的最好算法可以作到 O(n),但是那是一篇論文,這個作法我也還沒有研究過,底下先給出一個極巧妙且複雜度也可接受的作法。
假設有一個字串 T 滿足 TT 是 S 的子串,那麼我們可以把 S 每 |T| 格切成一塊,如:
S = abcdabbdabbab, T = dabb
-> S = |abcd|abbd|abba|b
這樣子會有什麼現象呢?我們注意到 TT 或者被切成兩份、或者被切成三份。不妨假設 TT 被切成三份,A|B|C,其中 A 的一部分後綴 A' 和 C 的一部分前綴 C' 屬於 TT。
(上面的例子中,A=abcd,B=abbd,C=abba,A 的後綴 d 和 C 的前綴 abb 屬於 TT)
這時候 A' 會是 A, B 的一個共同後綴,C' 則會是 B, C 的一個共同後綴,兩者會滿足 |A'|+|C'|=|T| (想一想,為什麼?)。
於是乎我們有下面的作法:
1. 構造 S 的 suffix array 和 height array
2. 構造 rev(S) 的 suffix array 和 height array,rev(S) 為 S 的顛倒字串,如 rev(abcde) = edcba
3. 枚舉 T 的長度 i
3.1. 將 S 每 i 格切成一塊
3.2. 計算任意相鄰兩塊的最長共同前綴長與最長共同後綴長 (這可以透過 1, 2 和 LCP 算法達成)
3.3. 若存在某塊滿足 「和前一塊的共同後綴長 x」+「和後一塊的共同前綴長 y」>= i,則代表存在長度是 i 的子串 T 滿足 TT 出現在 S 中
4. 取所有滿足 3.3. 的 i 中最大者與對應的子串即為我們的解
要注意的是 3.3. 的條件不能只取等號,例如 aaaaaaaa 就是一個只取等號會壞掉的反例;此外顯然 i <= |S|/2。
最後我們估計一下這個作法的複雜度:對於每個 i 共有 O(n/i) 塊,每塊要和前面、後面兩塊各進行一次 LCP 查詢 O(logn),總複雜度是
O( Σ(n/i) * logn ) = O(nlogn) * O(Σ1/i) = O(nlogn) * O(logn) = O(nlognlogn)
如果不清楚 Σ1/i 為什麼是 O(logn) 就先暫且接受這個結論吧 XD 有學過微積分的同學則可以透過 ∫dx/x = lgn 來理解這個結論。
|
|