跳轉到

4.2 最長共同子字串#

概念說明#

最長共同子字串（Longest Common Substring）要求比 LCS 更嚴格：共同的部分必須連續。例如 "abcdxyz" 與 "xyzabcd" 的最長共同子字串是 "abcd"（長度 4），而它們的 LCS 也是 "abcd"；但 "abab" 與 "baba" 的最長共同子字串是 "aba" 或 "bab"（長度 3），LCS 卻是 "aba"（長度 3）——在 "ababa" 與 "babab" 這類例子中，兩者的差距會更明顯：連續性是更強的「抄襲」證據。

兩種解法代表兩種思維：

解法一：動態規劃。 定義 dp[i][j] = 「以 s[i−1] 與 t[j−1] 結尾的最長共同子字串長度」。若 s[i−1] == t[j−1]，則 dp[i][j] = dp[i−1][j−1] + 1（兩邊同時向前延伸一格）；否則為 0（連續性斷裂，必須歸零——這正是與 LCS 轉移的關鍵差異）。答案是全表最大值，時間 O(mn)、空間可用滾動陣列降到 O(n)。

解法二：後綴結構。 把 s 與 t 拼成 s + "#" + t 建後綴陣列（3.3 節），計算 LCP 陣列；凡是「相鄰兩名後綴一個屬於 s、一個屬於 t」的 LCP 值，就是一個跨越兩字串的共同子字串，取最大即得答案。後綴樹的講法更優雅：建廣義後綴樹，找「子樹同時含兩串的葉子」的最深節點。此法建構 O(n)～O(n log n)、之後查詢線性，適合超大文字（如基因體、整本書）。

實務應用：抄襲偵測（連續雷同片段比 LCS 更能對應「整段照抄」）、基因體比對（找兩條 DNA 最長相同片段）、版本合併（找共同錨點段落）、檔案去重與差分同步（rsync 類工具找共同區塊）。第 10 章的抄襲偵測實戰將結合本章與指紋（fingerprint / shingling）技術。

演算法步驟#

DP 法： 1. 建表 dp，尺寸 (m+1)×(n+1)，第 0 列/行全 0。 2. 雙層迴圈填表：字元相同 → dp[i][j] = dp[i−1][j−1] + 1；否則 0。 3. 記錄全表最大值與其位置 (i, j)，子字串即 s[i−best : i]。 4. 可順帶記錄所有達到最大值的位置（可能有多個等長答案）。

後綴陣列法： 1. 拼接 u = s + "\x00" + t（分隔字元不得出現在原文）。 2. 建後綴陣列與 LCP 陣列（Kasai）。 3. 掃描相鄰名次對 (r−1, r)：若 (sa[r−1] < len(s)) != (sa[r] < len(s))（兩後綴分屬兩串），候選值為 lcp[r]。 4. 取所有候選的最大值，對應子字串為 u[sa[r] : sa[r] + lcp[r]]。

Python 程式碼範例#

def lcst_dp(s, t):
    """DP 法：O(mn) 時間、O(n) 空間"""
    m, n, best, end = len(s), len(t), 0, 0
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        cur = [0] * (n + 1)
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                cur[j] = prev[j - 1] + 1
                if cur[j] > best:
                    best, end = cur[j], i
        prev = cur
    return best, s[end - best:end]

def lcst_sa(s, t):
    """後綴陣列法：呼叫 3.3 節的 build_sa / build_lcp"""
    sep = "\x00"
    u = s + sep + t
    sa, rank = build_sa(u)
    lcp = build_lcp(u, sa, rank)
    best, at = 0, None
    for r in range(1, len(u)):
        i, j = sa[r - 1], sa[r]
        if (i < len(s)) != (j < len(s)):          # 分屬兩串
            if lcp[r] > best:
                best, at = lcp[r], i
    return best, (u[at:at + best] if best else "")

print(lcst_dp("abcdxyz", "xyzabcd"))     # (4, 'abcd')
print(lcst_dp("abab", "baba"))           # (3, 'aba')
print(lcst_dp("這是演算法課程", "我最喜歡演算法課程了"))   # (5, '演算法課程')
# print(lcst_sa("abcdxyz", "xyzabcd"))   # 接上 3.3 節程式碼即可驗證同結果

複雜度分析#

  • DP 法：時間 O(m×n)、空間 O(n)（滾動）；簡單可靠，適合數萬字以內的兩兩比較。
  • 後綴陣列法：建構 O(n log n)（SA-IS 可 O(n)）+ LCP O(n) + 掃描 O(n)，空間 O(n)；n = m 時遠優於 DP，且一次建好可對「多串取共同子字串」（廣義後綴樹）。
  • 多串推廣：k 個字串的共同子字串可用廣義後綴樹找「子樹含 k 種來源葉」的最深節點；DP 法在 k > 2 時需多維表，指數膨脹，不划算。
  • 注意 LCP 有個小陷阱：後綴陣列法中「相鄰對」可能同一串內部 LCP 更大但不跨串，必須檢查來源標記。

練習#

  1. 修改 lcst_dp，回傳所有等長的最長共同子字串及其在兩串中的起始位置。
  2. 把 3.3 節的 build_sa、build_lcp 貼進來，實作完整的 lcst_sa，在兩篇 5 萬字的文章上與 DP 法比對結果與執行時間。
  3. 實作「最長重複子字串」：對單一字串建後綴陣列，答案即 LCP 陣列最大值；驗證 "banana" 的答案是 "ana"，並對一段真實文章執行，觀察自然語言中最長重複片段的長度（通常對應片語或句型重複）。