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

問題描述

給定字符串 s（長度 ≤ 10^5），求其最長回文子串的長度。多組測試數據，EOF 結束。

Manacher 算法核心思想

將原字符串插入特殊字符（如 #）統一奇偶長度回文，得到新串 t（長度 2n+3，含首尾哨兵 $ 和 \0）。維護數組 p[i] 表示以 i 為中心的最長回文半徑（含中心）。利用對稱性與已知最右回文右邊界 mx 及其中心 id，在 O(1) 平均時間內獲取 p[i] 初始值，再暴力擴展。

關鍵步驟

1. 預處理：t = "$#a#b#a#\0" 形式，確保不越界。
2. 主循環：

   int mx = 0, id = 0;
   for (int i = 1; i < len; ++i) {
       p[i] = (mx > i) ? min(p[2*id - i], mx - i) : 1;
       while (t[i - p[i]] == t[i + p[i]]) ++p[i];
       if (i + p[i] > mx) { mx = i + p[i]; id = i; }
   }

3. 結果：max(p[i]) - 1 即原串最長回文長度。

代碼完整版

#include 
using namespace std;
const int MAXN = 200010;
char s[MAXN], t[MAXN];
int p[MAXN];

void manacher() {
    int n = strlen(s);
    t[0] = '$'; t[1] = '#';
    for (int i = 0, j = 2; i < n; ++i, j += 2) {
        t[j] = s[i]; t[j+1] = '#';
    }
    t[2*n+2] = '\0';
    int len = 2*n+2;
    int mx = 0, id = 0;
    for (int i = 1; i < len; ++i) {
        p[i] = (mx > i) ? min(p[2*id - i], mx - i) : 1;
        while (t[i - p[i]] == t[i + p[i]]) ++p[i];
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
    }
    int ans = 0;
    for (int i = 1; i < len; ++i) ans = max(ans, p[i]);
    printf("%d\n", ans - 1);
}

int main() {
    while (scanf("%s", s) != EOF) manacher();
    return 0;
}

常見錯誤與避坑

• p[i] = min(p[2*id-i], mx-i) 中 2*id-i 是對稱中心，不能 寫成 min(2*id-i, mx-i)（這是下標與值的混淆）。
• 哨兵 $ 和 # 必須不在輸入字符集中，保證邊界比較失敗。
• 數組大小需開 2*N+5 防止越界。

複雜度分析

每個字符最多參與一次成功的 while 擴展，總時間 O(n)，空間 O(n)。是線性時間回文算法的標準實現。