HDU 3068 詳解：Manacher 算法求最長回文子串 O(n)

題目大意

給定小寫字母字符串 S（長度 ≤ 110,000），多測試用例（≤ 120 組），求最長回文子串長度。回文：正反讀相同，如 "aba"、"abba"。

Manacher 算法核心思想

將奇/偶長度回文統一處理：在字符間插入特殊字符 #，首尾加 @ 和 $ 作為哨兵。

原串 "abba" → 轉換後 "@#a#b#b#a#$"

• 轉換後長度 = 2n + 3
• 所有回文在新串中均為奇長度，中心對應字符或 #
• 回文半徑 P[i] 含中心字符，原串回文長度 = P[i] - 1

算法流程

1. 預處理構建 str[]
2. 維護 maxRight（最右回文右邊界）和 center（對應中心）
3. 遍歷 i = 1..len-1：
   • 若 i < maxRight：利用對稱性 P[i] = min(P[mirror], maxRight - i)
   • 以 i 為中心暴力擴展
   • 更新 maxRight 和 center
   • 記錄最大 P[i]

完整代碼

#include 
using namespace std;
const int MAXN = 110010;
char s[MAXN], str[MAXN*2];
int P[MAXN*2];

void init() {
    str[0] = '@'; str[1] = '#';
    int n = 2;
    for (int i = 0; s[i]; ++i) {
        str[n++] = s[i];
        str[n++] = '#';
    }
    str[n] = 0;  // 結束符
}

int manacher() {
    int maxRight = 0, center = 0, ans = 0;
    for (int i = 1; str[i]; ++i) {
        // 利用對稱性初始化
        if (i < maxRight) {
            int mirror = 2*center - i;
            P[i] = min(P[mirror], maxRight - i);
        } else {
            P[i] = 1;
        }
        // 暴力擴展
        while (str[i - P[i]] == str[i + P[i]]) ++P[i];
        // 更新最右邊界
        if (i + P[i] > maxRight) {
            maxRight = i + P[i];
            center = i;
        }
        ans = max(ans, P[i]);
    }
    return ans - 1;  // 原串長度
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> s) {
        init();
        cout << manacher() << '\n';
    }
    return 0;
}

範例驗證

S = "aaaa"

str = @ # a # a # a # a #
P   = 1 2 3 4 5 4 3 2 1
max P[i] = 5 → 長度 4 ✓

S = "abab"

str = @ # a # b # a # b #
P   = 1 2 1 2 3 2 1 2 1
max P[i] = 3 → 長度 2 ("aba" 或 "bab") ✓

複雜度分析

• 時間：O(n) — 每字符最多參與一次成功擴展，對稱性初始化避免重複比較
• 空間：O(n) — str[] 和 P[]

關鍵點總結

1. 統一奇偶：插入 # 將所有回文轉為奇長度，簡化邏輯
2. 對稱性利用：i < maxRight 時，mirror = 2*center - i 的 P[mirror] 提供下界
3. 哨符：@ 和 $（或結束符 0）避免邊界檢查
4. 多測試用例：while(cin >> s) 讀取，空行自動跳過

總結

HDU 3068 是 Manacher 算法的模板題。O(n) 線性時間求最長回文子串是字符串算法的里程碑。核心在於「利用已知最右回文的對稱性避免重複擴展」，配合哨符簡化邊界。模板代碼值得熟記，可直接應用於最長回文子串、回文子串計數等問題。