Manacher（最长回文子串）CSP-S

💡 核心思想

Manacher 算法在 O(n) 时间内求出字符串中以每个字符为中心的最长回文半径。核心技巧是在字符间插入分隔符（如 #），将奇数长度和偶数长度的回文统一处理。利用对称性：如果当前点在已发现的最右回文串内部，则可以直接复制对称点的回文半径，只需少量扩展即可。

🎯 直觉理解

想象你在沙漠里探测地下水。你已经挖了一口井（一个回文串），深度为 p[mid]。现在要探测新位置 i，如果 i 在你已挖的井的范围内，那么 i 的对称点 j = 2*mid - i 已经被探测过了，你可以直接参考 j 的深度，只需要再往下挖一点点验证。

📝 算法流程

1. 在字符间插入 #，如 "aba" → "#a#b#a#"
2. 初始化 p[i] = 0，mid = 0，r = 0
3. 遍历每个位置 i：
4. 如果 i < r，则 p[i] = min(p[2*mid - i], r - i)
5. 中心扩展：while s[i+p[i]+1] == s[i-p[i]-1], p[i]++
6. 如果 i + p[i] > r，更新 mid = i, r = i + p[i]
7. 答案为 max(p[i]) - 1（因为插入了 #）

$$p[i] = \min(p[2 \cdot mid - i],\ r - i) \quad \text{（当 } i < r \text{ 时）}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

int manacher(const string& s) {
    int n = s.size();
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    
    int m = t.size();
    vector p(m, 0);
    int mid = 0, r = 0, maxLen = 0;
    
    for (int i = 0; i < m; i++) {
        if (i < r) p[i] = min(p[2 * mid - i], r - i);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m && 
               t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > r) { mid = i; r = i + p[i]; }
        maxLen = max(maxLen, p[i]);
    }
    return maxLen; // 回文半径（含 #），实际长度为 maxLen
}

string longestPalindrome(const string& s) {
    int n = s.size();
    string t = "#";
    for (char c : s) { t += c; t += '#'; }
    
    int m = t.size();
    vector p(m, 0);
    int mid = 0, r = 0, center = 0;
    
    for (int i = 0; i < m; i++) {
        if (i < r) p[i] = min(p[2 * mid - i], r - i);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < m && 
               t[i - p[i] - 1] == t[i + p[i] + 1]) p[i]++;
        if (i + p[i] > r) { mid = i; r = i + p[i]; }
        if (p[i] > p[center]) center = i;
    }
    
    int start = (center - p[center]) / 2;
    return s.substr(start, p[center]);
}

int main() {
    string s = "babad";
    cout << manacher(s) << endl;      // 3 ("bab" 或 "aba")
    cout << longestPalindrome(s) << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目