C++怎么实现Manacher算法_C++在线性时间内查找最长回文子串

Manacher算法通过预处理将字符串统一为奇数长度回文，利用对称性和已知回文半径数组P，在O(n)时间内求出最长回文子串；遍历中维护最右边界right和中心center，借助mirror减少重复扩展，最后根据P数组最大值定位原串起始位置并返回结果。

Manacher算法能在O(n)时间内找出字符串中最长回文子串，比暴力和动态规划更高效。C++实现的关键是预处理字符串并维护回文半径数组。

预处理字符串

在原字符串每个字符间插入特殊符号（如'#'），并在首尾添加不同边界符，避免越界。例如 "aba" 变为 "^#a#b#a#$"。

这样做可以把奇偶长度回文统一处理，所有回文都变为奇数长度。

维护回文半径数组 P

定义数组 P[i] 表示以位置 i 为中心的最长回文半径（不包含中心）。同时维护最右回文边界 right 和对应中心 center。

立即学习“C++免费学习笔记（深入）”；

遍历每个位置 i：

知了追踪

AI智能信息助手，智能追踪你的兴趣资讯

下载

• 如果 i 在 right 内，利用对称性：P[i] = min(right - i, P[2 * center - i])
• 尝试向外扩展，更新 P[i]
• 如果 i + P[i] > right，更新 center 和 right

提取最长回文

扫描 P 数组找到最大值及其位置，再映射回原字符串。

原串中起始位置为 (maxCenter - maxLen) / 2，长度为 maxLen。

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

#include 
#include 
#include 
using namespace std;

string longestPalindrome(string s) {
    if (s.empty()) return "";

    // 预处理字符串
    string transformed = "^#";
    for (char c : s) {
        transformed += c;
        transformed += '#';
    }
    transformed += '$';

    int n = transformed.size();
    vector P(n, 0);
    int center = 0, right = 0;

    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;

        if (i < right) {
            P[i] = min(right - i, P[mirror]);
        }

        // 尝试扩展
        while (transformed[i + P[i] + 1] == transformed[i - P[i] - 1]) {
            P[i]++;
        }

        // 更新中心和右边界
        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }
    }

    // 找最长回文
    int maxLen = 0, maxCenter = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            maxCenter = i;
        }
    }

    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

// 测试
int main() {
    string s = "babad";
    cout << longestPalindrome(s) << endl; // 输出 bab 或 aba
    return 0;
}

基本上就这些。核心是利用已知回文的对称性减少重复计算，达到线性时间复杂度。