竹園論壇

標題: 寒訊 String 主題之最長相鄰重複子序列 [打印本頁]

作者: ChinHuangLi@FB 時間: 2015-3-6 22:16
標題: 寒訊 String 主題之最長相鄰重複子序列
各位學弟妹：

很抱歉因為我一直忘記所以這篇文到現在才發 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 來理解這個結論。

歡迎光臨竹園論壇 (http://forum.tfcis.org/)