POJ 3974：Manacher 算法 O(n) 求最長回文子串

Manacher 算法核心思想

將原字符串插入特殊字符（如 '#'）統一奇偶長度回文，利用回文對稱性避免重複比較，線性時間求出每個中心的最大回文半徑。

預處理與數組定義

• s[]：新字符串，如 $#a#b#a#，長度 2n+3。
• p[i]：以 i 為中心的回文半徑（包含中心），即回文長度為 p[i]-1。
• id：當前最右回文的中心；mx = id + p[id] 為最右邊界。

核心遞推公式

void Manacher() {
    s[0] = '$'; s[1] = '#';
    for (int i = 0; i < len; ++i) {
        s[i*2+2] = str[i];
        s[i*2+3] = '#';
    }
    s[len*2+2] = 0;
    int mx = 0, id = 0, maxL = 0;
    for (int i = 1; i < len*2+2; ++i) {
        if (i < mx) p[i] = min(p[2*id - i], mx - i);
        else p[i] = 1;
        while (s[i + p[i]] == s[i - p[i]]) ++p[i];
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        if (p[i] > maxL) maxL = p[i];
    }
    printf("%d\n", maxL - 1);
}