Manacher（最长回文子串）NOI

💡 核心思想

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

🎯 直觉理解

Manacher 求最长回文子串，$O(n)$。回文就是"正着读反着读一样"，如 aba、abba。朴素做法枚举中心向两边扩展是 $O(n^2)$，Manacher 利用已算出的回文对称性加速。

技巧：先在字符间插入分隔符（如 #a#b#a#），让奇偶长度的回文统一处理；维护当前最右回文边界 R 和它的中心 C——对称位置的回文半径可以直接借用，只在需要时才继续向外扩展。

理解"复用"：因为回文是对称的，左半边算过的信息可以直接翻到右半边，这就是 $O(n)$ 的来源。实现上 d 数组存回文半径，答案是最大值减 1。

📝 算法流程

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;
}

⚠️ 常见坑点

📚 相关题目