HDU 3068 最長回文：Manacher 算法 O(n) 線性解法模板

題目描述

給定小寫字母字符串 S，求最長回文子串長度。回文正讀反讀相同（如 aba, abba）。

Manacher 算法核心思想

1. 統一奇偶長度：在字符間插入特殊符號 #（或 0），如 "abba" → "#a#b#b#a#"，所有回文變為奇長度，中心必在字符或 # 上。
2. 維護最右回文：變量 mx（最右邊界），id（對應中心）。利用對稱性避免重複匹配。
3. 回文半徑數組 p[i]：以 i 為中心的回文半徑（含中心），原串長度 = p[i] - 1。

關鍵擴展邏輯

if (i < mx) p[i] = min(mx - i, p[2*id - i]); // 利用對稱性初始化
else p[i] = 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];   // 暴力擴展
if (i + p[i] > mx) { mx = i + p[i]; id = i; } // 更新最右回文

完整 C++ 模板代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 110009;
char s[N], t[N<<1];
int p[N<<1];

int manacher(int len) {
    int id = 1, mx = 0;
    p[0] = 1;
    for (int i = 1; i < len; ++i) {
        if (i < mx) p[i] = min(mx - i, p[2*id - i]);
        else p[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 = 1;
    for (int i = 1; i < len; ++i) ans = max(ans, p[i] - 1);
    return ans;
}

int main() {
    while (scanf("%s", s) == 1) {
        int len = strlen(s);
        t[0] = '$'; // 哨兵，避免越界
        for (int i = 0; i < len; ++i) {
            t[2*i+1] = '#';
            t[2*i+2] = s[i];
        }
        t[2*len+1] = '#';
        t[2*len+2] = '\0';
        printf("%d\n", manacher(2*len+2));
    }
    return 0;
}

複雜度分析

• 時間 O(n)：每字符最多參與一次成功匹配，mx 單調遞增。
• 空間 O(n)：轉換字符串 + 半徑數組。

易錯點總結

• 哨兵 t[0] = '$'（不在字符集中）防止 i-p[i] 越界。
• 特殊字符 # 必須不在原字符集中。
• 答案取 p[i] - 1 還原原串長度。
• 輸入可能多行，用 while(scanf("%s",s)==1) 循環讀取。

延伸應用

• 最長回文子串內容：記錄最大 p[i] 對應的 id，回推原串區間。
• 回文子串個數統計：sum += p[i]/2。
• 帶約束回文（如 HDU 4513 非遞減）：擴展條件增加額外判斷。