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

問題描述

給定長度 ≤ 110,000 的小寫字母字符串，求最長回文子串長度。多測試用例，空行分隔。

Manacher 算法核心思想

利用回文對稱性避免重複比較。預處理插入特殊字符（如 #），統一奇偶長度回文。

關鍵數組

• p[i]：以處理後字符串第 i 位為中心的回文半徑（包含中心）。
• maxRight：當前已知最右回文邊界 center + p[center]。
• center：對應的中心位置。

遞推公式

對於位置 i：

• 若 i < maxRight，利用對稱點 j = 2*center - i，p[i] = min(p[j], maxRight - i)。
• 以此為起點向兩側暴力擴展。
• 若 i + p[i] > maxRight，更新 center = i, maxRight = i + p[i]。

完整代碼

#include 
using namespace std;

const int MAXN = 220005;
char s[MAXN/2], str[MAXN];
int p[MAXN];

void manacher() {
    int len = strlen(s);
    str[0] = '$'; str[1] = '#';
    for (int i = 0; i < len; i++) {
        str[i*2+2] = s[i];
        str[i*2+3] = '#';
    }
    int n = len * 2 + 2;
    str[n] = '\0';
    
    int maxRight = 0, center = 0, ans = 0;
    for (int i = 1; i < n; i++) {
        p[i] = (maxRight > i) ? min(p[2*center - i], maxRight - 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] - 1); // 原始長度
    }
    printf("%d\n", ans);
}

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

複雜度分析

• 時間：O(n)，每個字符最多被比較一次。
• 空間：O(n)。

關鍵細節

• 哨兵字符 $ 和 # 避免越界並統一奇偶。
• p[i] - 1 為原始字符串中的回文長度。
• 輸入以空行分隔，scanf("%s") 自動跳過空白。

總結

Manacher 算法是求最長回文子串的標準 O(n) 解法。核心在於維護「最右邊界」與「中心對稱」性質，將中心擴展法優化為線性。模板值得熟練背誦。