查看: 920|回復: 0

寒訊 String 主題 之 最長相鄰重複子序列

[複製鏈接]
  • TA的每日心情
    哭哭
    2015-5-8 16:37
  • 簽到天數: 13 天

    [LV.3]偶爾看看II

    6

    主題

    22

    帖子

    101

    積分

    高一新生

    Rank: 2

    積分
    101
    發表於 2015-3-6 22:16:54 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    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 來理解這個結論。


    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表