Manacher：最長回文子字串#

問題#

給一個字串，找出其中最長的回文子字串（順讀逆讀相同的連續片段）。例如 babad 的答案是 bab（或 aba），cbbd 的答案是 bb。

這是經典的 最長回文子字串 ↗。難點在於回文有兩種形態：

  • 奇數長度：以單一字元為中心，如 aba；
  • 偶數長度：以兩字元之間的縫隙為中心，如 abba。

要同時處理這兩種中心，是樸素解法寫起來最囉嗦的地方，也是 Manacher 第一步要先抹平的。

樸素法：中心擴展 O(n²)#

最直覺的做法是枚舉每個可能的中心，再往左右兩側同步擴展，看能延伸多遠。

為了不必為奇偶兩種回文寫兩套邏輯，先做一個經典預處理：在每兩個字元之間、以及首尾都插入一個分隔符 #，並在最前面放一個哨兵字元（例如 ^）。這樣處理後：

原字串：    a b b a
轉換後：  ^ # a # b # b # a #

轉換後的字串長度恆為奇數，任何回文（不論原本奇偶）在新串裡都成了以某個字元為中心的奇數長度回文。偶數回文 abba 的中心，正好落在中間那個 # 上。哨兵的作用是當作邊界圍牆，讓向左擴展時不必額外判斷是否越界——遇到不存在的字元自然就停下。

fun longestPalindrome(s: String): String {
    if (s.isEmpty()) return ""

    // 預處理：插入分隔符與哨兵，統一成奇數長度
    // 尾端放另一個哨兵，避免向右越界
    val sb = StringBuilder("^")
    for (c in s) {
        sb.append('#').append(c)
    }
    sb.append("#$")
    val t = sb.toString()

    var bestCenter = 0
    var bestRadius = 0
    for (i in 1 until t.length - 1) {
        var r = 0
        // 以 i 為中心向左右擴展
        while (t[i - r - 1] == t[i + r + 1]) {
            r++
        }
        if (r > bestRadius) {
            bestRadius = r
            bestCenter = i
        }
    }

    // 還原回原字串的座標：去掉 # 後，半徑即為原回文長度
    val start = (bestCenter - bestRadius) / 2  // 對應原字串起點
    return s.substring(start, start + bestRadius)
}

每個中心最多擴展 O(n) 次，共 O(n) 個中心，總體 O(n²)。問題出在：不同中心的擴展過程彼此完全獨立，重複比較了大量字元。回文是高度對稱的結構，這些重複比較其實有跡可循。

Manacher：如何降到 O(n)#

Manacher 的本質，是把「中心擴展」改造成一個建立在已知資訊上的 DP：用左半邊已經算好的回文半徑，預測右半邊的回文能延伸多遠，從而跳過大量重複比較。

延續上面的預處理（每個位置都是奇數中心）。我們用一個陣列 p[i] 記錄以 i 為中心的回文半徑，並在掃描過程中維護兩個關鍵變數：

  • C：目前已知最右回文的中心；
  • R：該回文的右邊界（即 C + p[C]）。

[C, R] 描述了「目前我們對字串右側的探索已經到達哪裡」。掃到新位置 i 時，只要 i 還落在 R 以內，它關於 C 的鏡像位置 i' = 2*C - i 的回文半徑 p[i'] 早就算好了——因為 [2C-R, R] 這整段是回文，左右對稱，i' 附近的結構會「複製」到 i 附近。我們就能用 p[i'] 當作 p[i] 的起跳值，省掉從 0 開始的擴展。

關鍵在於：這個「複製」只在鏡像回文沒有捅破 [C, R] 邊界時才完全成立，否則邊界外的對稱性是未知的，必須親自驗證。於是依 i 與 R 的關係分三種情況。

三種情況的處理（核心）

設 i' = 2*C - i 為鏡像位置。

情況一：i 在 R 內，且鏡像回文未觸及左邊界

即 p[i'] 完全包在 [2C-R, R] 對應的左半邊裡（i + p[i'] < R）。此時左右兩側結構完全對稱，可直接斷定：

p[i] = p[i']   // 完全照抄，連一次比較都不用

情況二：鏡像回文恰好觸及左邊界

即 i + p[i'] == R（鏡像回文延伸到 [C,R] 的左端）。此時 p[i] 至少有 p[i'] 這麼大，但 R 以外是否還能繼續延伸，左半邊沒有提供任何資訊：

p[i] = R - i   // 先吃滿到邊界，再嘗試往外擴展

情況三：i 超出 R（落在已知回文之外）

沒有任何鏡像資訊可借，退化回普通中心擴展，起跳半徑為 0：

p[i] = 0       // 老老實實從頭擴展

統一寫法：先取一個保守的初始值 p[i] = min(R - i, p[2C-i])（當 i < R 時），否則 p[i] = 0；接著無論哪種情況，都再嘗試 while 向外擴展。情況一通常一次擴展就失敗（因為對稱性已保證它不會更大），情況二、三才真正往外推進。每次成功擴展若使回文越過了舊的 R，就更新 C 與 R。

為什麼是 O(n)？ 關鍵不在於每個 i 花多少時間，而在於 while 擴展的總次數。每一次成功的向外擴展，都會讓右邊界 R 嚴格往右移動至少一格；而 R 從頭到尾只能單調增加、最多走到字串末端，因此整個過程中擴展的總次數是 O(n)。再加上每個位置 O(1) 的起跳計算，全程線性。

完整實作：

fun longestPalindrome(s: String): String {
    if (s.isEmpty()) return ""

    // 預處理：^ # a # b # ... # $
    val sb = StringBuilder("^")
    for (c in s) {
        sb.append('#').append(c)
    }
    sb.append("#$")
    val t = sb.toString()
    val n = t.length

    val p = IntArray(n)      // p[i]：以 i 為中心的回文半徑
    var center = 0
    var right = 0            // 目前最右回文的中心 C 與右邊界 R

    for (i in 1 until n - 1) {
        // 借用鏡像位置的結果作為起跳值（情況一 / 二）；超出 R 則為 0（情況三）
        if (i < right) {
            val mirror = 2 * center - i
            p[i] = minOf(right - i, p[mirror])
        }

        // 無論哪種情況，都嘗試繼續向外擴展
        while (t[i - p[i] - 1] == t[i + p[i] + 1]) {
            p[i]++
        }

        // 若回文越過舊邊界，更新 C 與 R
        if (i + p[i] > right) {
            center = i
            right = i + p[i]
        }
    }

    // 找出最大半徑及其中心，還原回原字串
    var bestRadius = 0
    var bestCenter = 0
    for (i in 1 until n - 1) {
        if (p[i] > bestRadius) {
            bestRadius = p[i]
            bestCenter = i
        }
    }
    val start = (bestCenter - bestRadius) / 2
    return s.substring(start, start + bestRadius)
}

p[i] 在轉換串上的半徑，恰好等於原字串中對應回文的長度，這是 # 插入後的一個漂亮巧合：原回文每個字元在轉換串中都被一個 # 隔開，半徑數正好把長度「數」了出來。

小結#

方法時間複雜度空間核心想法適用
中心擴展O(n²)O(n)枚舉每個中心向外擴展字串不長、求快速可讀的解
ManacherO(n)O(n)用鏡像位置已算結果跳過重複比較大字串、要求最優複雜度

兩者都先用 # 把奇偶回文統一成奇數中心。差別只在於 Manacher 多維護了 [C, R] 這個「已探索的最右回文」，把中心擴展裡被白白浪費的對稱資訊回收利用——這正是「消除重複計算」這條優化主線在字串問題上的又一次體現。

延伸閱讀：回到 字串匹配基礎 複習回文與字串問題的共通預處理技巧。

Backward 單詞搜尋 遞迴與分治 Forward