一、算法概述

Manacher 算法是一种在 线性时间 O(n) 内求解字符串中最长回文子串的高效算法。由 Glenn Manacher 于 1975 年提出，相比朴素的中心扩展法 O(n²) 和动态规划法 O(n²)，它将时间复杂度降到了最优的 O(n)。

---

二、核心思想

Manacher 算法的核心思想包括两个关键技巧：

1. 插入分隔符，统一处理奇偶回文

   • 在字符串每个字符之间（包括首尾）插入一个特殊分隔符（通常用 #），使得所有回文串的长度都变为奇数，从而可以用统一的中心扩展方式处理。
   • 例如："aba" → "#a#b#a#"，"aa" → "#a#a#"。

2. 利用已知回文信息避免重复计算

   • 维护一个回文半径数组 p[i]，表示以位置 i 为中心的最长回文半径。
   • 维护当前最右回文边界 R 及其对应的中心 C。当计算 p[i] 时，利用 i 关于 C 的对称点 mirror = 2*C - i 的已知信息，进行加速。

---

三、算法步骤 / 伪代码

输入：原始字符串 s
输出：最长回文子串

1. 预处理：在 s 的每个字符间插入 '#'，并在首尾加哨兵 '^' 和 '$'，得到字符串 t
2. 初始化数组 p[0..n-1] = 0，回文中心 C = 0，最右边界 R = 0
3. 遍历 i = 1 到 n-1：
   a. 计算镜像位置 mirror = 2*C - i
   b. 如果 i < R，则 p[i] = min(R - i, p[mirror])
   c. 以 i 为中心向两边扩展，更新 p[i]
   d. 如果 i + p[i] > R，则更新 C = i，R = i + p[i]
4. 找到 p[i] 的最大值及其中心 maxCenter
5. 从原始字符串 s 中提取最长回文子串

---

四、C++ 代码实现

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Manacher {
public:
    // 求最长回文子串，返回 (长度, 子串)
    pair<int, string> longestPalindrome(const string& s) {
        if (s.empty()) return {0, ""};

        // 1. 预处理：插入分隔符
        string t = preprocess(s);
        int n = t.size();
        vector<int> p(n, 0);  // 回文半径数组

        // 2. Manacher 核心
        int C = 0;  // 当前最右回文串的中心
        int R = 0;  // 当前最右回文串的右边界

        for (int i = 1; i < n - 1; i++) {
            // 利用镜像初始化 p[i]
            int mirror = 2 * C - i;
            if (i < R) {
                p[i] = min(R - i, p[mirror]);
            }

            // 中心扩展
            while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
                p[i]++;
            }

            // 更新最右边界
            if (i + p[i] > R) {
                C = i;
                R = i + p[i];
            }
        }

        // 3. 找到最大回文半径及其中心
        int maxLen = 0;
        int centerIdx = 0;
        for (int i = 1; i < n - 1; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                centerIdx = i;
            }
        }

        // 4. 从原字符串中提取最长回文子串
        // 原始字符串中的起始位置 = (centerIdx - maxLen) / 2
        int start = (centerIdx - maxLen) / 2;
        string result = s.substr(start, maxLen);

        return {maxLen, result};
    }

private:
    // 预处理：插入分隔符和哨兵
    // 原始: "aba"  →  "^#a#b#a#$"
    string preprocess(const string& s) {
        string t = "^";
        for (char c : s) {
            t += "#";
            t += c;
        }
        t += "#$";
        return t;
    }
};

// ==================== 测试用例 ====================
int main() {
    Manacher m;

    // 测试1: 奇数长度回文
    auto [len1, str1] = m.longestPalindrome("babad");
    cout << "输入: babad" << endl;
    cout << "最长回文子串: " << str1 << " (长度: " << len1 << ")" << endl;
    cout << endl;

    // 测试2: 偶数长度回文
    auto [len2, str2] = m.longestPalindrome("cbbd");
    cout << "输入: cbbd" << endl;
    cout << "最长回文子串: " << str2 << " (长度: " << len2 << ")" << endl;
    cout << endl;

    // 测试3: LeetCode 5 示例
    auto [len3, str3] = m.longestPalindrome("abbcacacab");
    cout << "输入: abbcacacab" << endl;
    cout << "最长回文子串: " << str3 << " (长度: " << len3 << ")" << endl;
    cout << endl;

    // 测试4: 全部相同字符
    auto [len4, str4] = m.longestPalindrome("aaaaaa");
    cout << "输入: aaaaaa" << endl;
    cout << "最长回文子串: " << str4 << " (长度: " << len4 << ")" << endl;
    cout << endl;

    // 测试5: 单字符
    auto [len5, str5] = m.longestPalindrome("a");
    cout << "输入: a" << endl;
    cout << "最长回文子串: " << str5 << " (长度: " << len5 << ")" << endl;
    cout << endl;

    // 测试6: 空字符串
    auto [len6, str6] = m.longestPalindrome("");
    cout << "输入: (空)" << endl;
    cout << "最长回文子串: " << str6 << " (长度: " << len6 << ")" << endl;

    return 0;
}

---

五、复杂度分析

复杂度类型	分析
时间复杂度	O(n) — 虽然有两层循环，但内层 while 每次成功扩展都会使 R 增大，而 R 最多从 0 增长到 n，所以总扩展次数为 O(n)。每个字符最多被访问常数次。
空间复杂度	O(n) — 需要存储预处理后的字符串 t（长度约 2n+3）和回文半径数组 p（长度约 2n+3）。

---

六、应用场景

1. 最长回文子串：字符串处理中最经典的问题（LeetCode 5）。
2. 回文子串计数：统计一个字符串中有多少个回文子串（LeetCode 647）。
3. 分割回文串：判断能否将字符串分割成若干回文子串。
4. DNA 序列中的回文结构：生物信息学中寻找回文序列。
5. 文本编辑器：检测对称文本模式。
6. 竞赛编程：几乎所有涉及回文串的高效问题。

---

七、经典例题

LeetCode 5. 最长回文子串

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。

示例：

• 输入: "babad"，输出: "bab"（"aba" 也是有效答案）
• 输入: "cbbd"，输出: "bb"

解法说明：使用上述 Manacher 算法，O(n) 时间内即可解决。预处理后遍历一遍，维护回文半径数组，最后根据最大半径和中心点位置还原最长回文子串。上述 C++ 代码可直接解答此题。

---

说明：以上 C++ 代码完整可编译，使用 g++ -std=c++17 -O2 filename.cpp -o main 编译后直接运行即可看到所有测试用例的输出。