P4895 输出最长回文子串（提高）

解题思路

第一步，读懂题目。 给一个长度为 N 的字符串，找出其中最长的回文子串（正着读和倒着读一样）。如果有多个长度相同的，输出最靠前的那一个。

第二步，为什么要用 Manacher。 N 最大是 10000。如果对每个位置都向两边慢慢扩展去找回文，最坏情况（比如全是同一个字母）要花 O(N²) 的时间，大约是 10⁸ 次，可能超时。Manacher 算法利用"回文串左右对称"的性质，把时间降到 O(N)。

第三步，统一处理奇偶。 在原始字符串的每个字符之间插入一个特殊符号 #，例如 "abc" 变成 "#a#b#c#"。这样原来偶数长度的回文（如 "aa"）也会有一个中心。再维护一个数组 d[i] 表示以第 i 个位置为中心能扩展到多大的半径。

第四步，借助已经算过的答案。 当我们算到中心 i 时，如果 i 在之前某个大回文范围内，那么以 i 为中心的回文半径至少等于它关于大回文中心对称的点的半径（但不能超出大回文的右边界）。用这个初始值再继续向外扩展，就能省掉大量重复比较。

第五步，还原答案。 对每个中心 i，半径 len=d[i]-1 对应原串的一个回文，起点是 (i-len)/2。找最大的 len，长度相同就选起点更靠前的，最后输出这一段。

具体例子： "baacaaba" 中，"baacaab" 是长度为 7 的回文（整个串不是回文），Manacher 找到它并输出。

参考代码

// 输出最长回文子串：Manacher算法O(N),输出第1个最长的回文子串
#include <iostream>
using namespace std;

int n, l, d[20005];      // d[i]为以i为中心的回文半径
char s[10005], t[20005]; // s原串, t插入#后的新串

int main() {
    cin >> s;
    for (n = 0; s[n]; n++); // 求原串长度
    l = 0; t[l++] = '#';
    for (int i = 0; i < n; i++) { t[l++] = s[i]; t[l++] = '#'; }
    int mx = 0, p = 0;      // mx为最右边界, p为对应中心
    for (int i = 0; i < l; i++) {
        int r = (i < mx) ? (d[2 * p - i] < mx - i + 1 ? d[2 * p - i] : mx - i + 1) : 1;
        while (i - r >= 0 && i + r < l && t[i - r] == t[i + r]) r++;
        d[i] = r;
        if (i + r - 1 > mx) { mx = i + r - 1; p = i; }
    }
    int best = 0, st = 0;   // best最长长度, st起始下标
    for (int i = 0; i < l; i++) {
        int len = d[i] - 1;               // 原串回文长度
        int pos = (i - len) / 2;          // 原串起始下标
        if (len > best) { best = len; st = pos; }
        else if (len == best && pos < st) st = pos; // 同长取靠前
    }
    for (int i = st; i < st + best; i++) cout << s[i];
    cout << endl;
    return 0;
}

复杂度分析

Manacher 算法中每个位置最多被扩展一次，所以时间复杂度是 O(N)，N 最大 10000，非常快。空间上需要存插入 # 后的新串和半径数组，都是 O(N)。