Manacher算法详解（C++实现最长回文子串的高效解法）

算法步骤详解

假设原字符串为 s，我们构造新字符串 t，并在其上定义数组 P，其中 P[i] 表示以 t[i] 为中心的最长回文半径（包含中心）。

算法流程如下：

1. 预处理：在 s 的每个字符间插入特殊字符（如 '#'），首尾也加哨兵（如 '^' 和 '$' 防越界）。
2. 初始化：C = 0（当前回文中心），R = 0（当前最右边界）。
3. 遍历 t 中每个位置 i：
• 若 i < R，则利用对称性：P[i] = min(R - i, P[2*C - i])。
• 尝试以 i 为中心向外扩展，更新 P[i]。
• 若扩展后超出 R，更新 C = i 和 R = i + P[i]。
4. 最终答案：原字符串中最长回文子串长度为 max(P) - 1。

C++ 代码实现

下面是一个完整的、可运行的 C++ 实现：

#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;string preprocess(const string& s) {    // 在字符串前后加上哨兵，中间插入 '#'    string t = "^#";    for (char c : s) {        t += c;        t += '#';    }    t += "$";    return t;}string longestPalindrome(const string& s) {    if (s.empty()) return "";    string t = preprocess(s);    int n = t.length();    vector<int> P(n, 0);    int C = 0, R = 0; // 当前中心和最右边界    for (int i = 1; i < n - 1; i++) {        // 利用对称性        int mirror = 2 * C - i;        if (i < R) {            P[i] = min(R - i, P[mirror]);        }        // 尝试扩展        while (t[i + (1 + P[i])] == t[i - (1 + P[i])]) {            P[i]++;        }        // 更新中心和右边界        if (i + P[i] > R) {            C = i;            R = i + P[i];        }    }    // 找到最大回文半径及其位置    int maxLen = 0, centerIndex = 0;    for (int i = 1; i < n - 1; i++) {        if (P[i] > maxLen) {            maxLen = P[i];            centerIndex = i;        }    }    // 转换回原字符串的起始位置    int start = (centerIndex - maxLen) / 2;    return s.substr(start, maxLen);}int main() {    string s = "babad";    cout << "最长回文子串: " << longestPalindrome(s) << endl;    return 0;}  

关键点解析

• 预处理：通过插入 '#'，将所有回文统一为奇数长度，简化逻辑。
• 对称性利用：当 i 在 R 内时，其对称点 mirror 的回文信息可直接复用，但不能超过 R - i。
• 线性时间：每个字符最多被访问两次（一次扩展，一次被跳过），因此总时间复杂度为 O(n)。

总结

Manacher算法 是解决 最长回文子串 问题的最优解之一，特别适合在竞赛或高性能场景中使用。通过本文的讲解和 C++ 代码示例，相信你已经掌握了这一强大工具。

记住，理解算法的核心思想比死记代码更重要。多动手实践，尝试修改输入字符串，观察 P 数组的变化，你会对 字符串算法 有更深的体会！

希望这篇教程对你有帮助！如果你喜欢，请分享给更多学习 C++回文字符串 处理的朋友吧！