PAT 1040 Longest Symmetric String - Manacher 算法求最長回文子串

問題描述

給定長度 ≤ 1000 的字符串，求最長對稱子串（回文子串）長度。

範例： Is PAT&TAP symmetric? → 最長回文 s PAT&TAP s，長度 11。

Manacher 算法核心思想

1. 預處理：在字符間插入特殊字符（如 #），統一奇偶長度回文處理
2. 維護最右回文：center 為當前最右回文中心，right 為最右邊界
3. 利用對稱性：i 在 center 內時，鏡像點 j = 2*center - i 的半徑可作為初始值
4. 中心擴展：從初始半徑開始暴力擴展，更新 center/right

預處理示例

原串:  a b b a
新串: # a # b # b # a #  (首尾加 ^ $ 或哨兵)
索引: 0 1 2 3 4 5 6 7 8

C++ 完整實現

#include 
#include 
using namespace std;

const int MAXN = 2010;
char s[MAXN];
int p[MAXN];  // 回文半徑（含中心）

int manacher() {
    int n = 0;
    s[n++] = '$';  // 左哨兵
    s[n++] = '#';
    int ch;
    while ((ch = getchar()) != '\n' && ch != EOF) {
        s[n++] = ch;
        s[n++] = '#';
    }
    s[n] = '\0';
    
    int center = 0, right = 0, maxLen = 0;
    for (int i = 1; i < n; ++i) {
        // 利用對稱性獲取初始半徑
        p[i] = (right > i) ? min(p[2*center - i], right - i) : 1;
        
        // 中心擴展
        while (s[i + p[i]] == s[i - p[i]]) ++p[i];
        
        // 更新最右回文
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        maxLen = max(maxLen, p[i] - 1);  // 扣除插入的 #
    }
    return maxLen;
}

int main() {
    printf("%d\n", manacher());
    return 0;
}

關鍵點解析

複雜度分析

• 時間：O(n)，每個字符最多被比較常數次
• 空間：O(n)，新串長度 2n+3

對比：中心擴展法 O(n²)

// 簡單但較慢，n=1000 也能過
int expand(const string& s, int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) { --l; ++r; }
    return r - l - 1;
}
int longestPalindrome(string s) {
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        ans = max(ans, expand(s, i, i));     // 奇數長度
        ans = max(ans, expand(s, i, i+1));   // 偶數長度
    }
    return ans;
}

Manacher 是線性時間的最優解，適合大數據量場景。