C++ Manacher 算法：原理、实现与应用

Manacher 算法（马拉车算法）是专门解决最长回文子串问题的线性时间算法，由 Glenn Manacher 在 1975 年提出。它通过对字符串进行预处理（插入特殊字符）消除奇偶回文的差异，并利用'回文对称性'记录已遍历区域的信息，避免重复计算，将时间复杂度从中心扩展法的 O(n^2) 降至 O(n)。本文将从核心原理、预处理、算法流程到实战优化，全面解析 Manacher 算法的设计思想与 C++ 实现技巧。

一、Manacher 算法的核心背景与优势

1.1 问题引入：中心扩展法的瓶颈

最长回文子串的经典解法是中心扩展法：遍历每个字符（奇数长度回文的中心）和每两个字符之间的间隙（偶数长度回文的中心），向两边扩展直到字符不匹配。

// 中心扩展法示例（O(n^2)）
int expand(const string& s, int l, int r) {
    while (l >= 0 && r < s.size() && s[l] == s[r]) {
        l--; r++;
    }
    return r - l - 1; // 回文长度
}
string longestPalindrome_brute(const string& s) {
    if (s.empty()) return "";
    int start = 0, max_len = 0;
    for (int i = 0; i < s.size(); ++i) {
        int len1 = expand(s, i, i); // 奇数长度
        int len2 = expand(s, i, i+1); // 偶数长度
        int len = max(len1, len2);
        if (len > max_len) {
            max_len = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substr(start, max_len);
}

缺陷：对每个中心都要重复扩展，最坏情况下（如全为相同字符的字符串）时间复杂度为 O(n^2)，数据量大时效率极低。

1.2 Manacher 算法的核心改进

Manacher 算法通过两个关键优化实现线性时间：

预处理字符串：插入特殊字符（如 #），将奇偶长度的回文统一为奇数长度（如 abba → #a#b#b#a#），避免分别处理奇偶情况；
利用回文对称性：维护「右边界最远的回文子串」的中心 center 和右边界 right，对于当前位置 i，若 i 在 right 内，可通过对称位置 mirror = 2*center - i 的回文长度，直接得到 i 的初始回文长度，避免重复扩展。

1.3 核心概念定义

给定预处理后的字符串 t（如 s=abba → t=#a#b#b#a#），定义：

p 数组：p[i] 表示以 t[i] 为中心的最长回文子串的半径（即从中心到右边界的字符数，包含中心）；
- 例如 t=#a#b#b#a#，p[4]=4（中心为 t[4]，回文半径 4，对应原字符串的 abba，长度为 p[i]-1）；
center：当前右边界最远的回文子串的中心位置；
right：当前右边界最远的回文子串的右边界位置；
回文长度转换：预处理后回文半径 p[i] → 原字符串回文长度 = p[i] - 1；
起始位置转换：预处理后中心 i → 原字符串起始位置 = (i - p[i]) / 2。

示例：s=abba → t=#a#b#b#a#，p 数组为 [0,1,0,1,4,1,0,1,0]：

p[4]=4 → 原回文长度 = 4-1=4（对应 abba）；
起始位置 = (4-4)/2 = 0（对应原字符串的第 0 位）。

二、Manacher 算法的完整实现

2.1 步骤 1：预处理字符串

插入特殊字符 #，并在首尾添加不同的边界字符（如 ^ 和 $），避免越界判断：

// 预处理字符串：s → ^#s[0]#s[1]#...#s[n-1]#$
string preprocess(const string& s) {
    int n = s.size();
    if (n == 0) return "^$";
    string res = "^"; // 左边界
    for (int i = 0; i < n; ++i) {
        res += "#" + s.substr(i, 1);
    }
    res += "#$"; // 右边界
    return res;
}

2.2 步骤 2：核心算法实现

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

// Manacher 算法：返回最长回文子串
string manacher(const string& s) {
    string t = preprocess(s);
    int n = t.size();
    vector<int> p(n, 0); // p 数组：存储回文半径
    int center = 0, right = 0; // 当前最右回文的中心和右边界

    // 遍历预处理后的字符串（跳过边界^和$）
    for (int i = 1; i < n - 1; ++i) {
        // 步骤 1：计算对称位置
        int mirror = 2 * center - i; // i 关于 center 的对称位置
        // 步骤 2：初始化 p[i]（利用对称性）
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }
        // 步骤 3：中心扩展（核心）
        while (t[i + p[i] + 1] == t[i - (p[i] + 1)]) {
            p[i]++;
        }
        // 步骤 4：更新 center 和 right（如果当前回文右边界超过 right）
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }

    // 步骤 5：找到 p 数组中的最大值（最长回文半径）
    int max_len = 0, center_idx = 0;
    for (int i = 1; i < n - 1; ++i) {
        if (p[i] > max_len) {
            max_len = p[i];
            center_idx = i;
        }
    }

    // 步骤 6：转换为原字符串的起始位置和长度
    int start = (center_idx - max_len) / 2;
    return s.substr(start, max_len);
}

// 测试代码
int main() {
    vector<string> test_cases = {"abba", "cbbd", "a", "ac", "ccc", "abcba"};
    for (const string& s : test_cases) {
        string res = manacher(s);
        cout << "原字符串：" << s << " → 最长回文子串：" << res << endl;
    }
    return 0;
}

输出结果：

原字符串：abba → 最长回文子串：abba
原字符串：cbbd → 最长回文子串：bb
原字符串：a → 最长回文子串：a
原字符串：ac → 最长回文子串：a
原字符串：ccc → 最长回文子串：ccc
原字符串：abcba → 最长回文子串：abcba

2.3 关键代码解析

预处理逻辑：
- 插入 # 后，所有回文子串均为奇数长度（如 abba → #a#b#b#a#，回文中心为第 4 位的 #）；
- 首尾添加 ^ 和 $，确保扩展时 t[i+p[i]+1] 和 t[i-(p[i]+1)] 不会越界，无需额外判断。
对称位置计算：
- mirror = 2*center - i：是 i 关于 center 的对称点（如 center=4，i=5 → mirror=3）；
- 若 i < right，p[i] 初始值取 min(right-i, p[mirror])：
  - right-i：保证 i+p[i] 不超过当前右边界 right；
  - p[mirror]：利用对称位置的回文长度，避免重复扩展。
中心扩展：
- 仅当初始 p[i] 扩展后仍能匹配时，才继续扩展，大幅减少重复计算。
结果转换：
- 原字符串回文长度 = p[i]（预处理后的半径） - 1；
- 原字符串起始位置 = (i - p[i]) / 2：因预处理字符串中每个原字符前都有 #，需除以 2 还原。

三、Manacher 算法的进阶优化

3.1 空间优化：省略预处理字符串

可通过数学计算直接映射原字符串索引和预处理后的索引，避免额外存储预处理字符串：

// 空间优化版 Manacher（无需显式预处理字符串）
string manacher_optimized(const string& s) {
    int n = s.size();
    if (n == 0) return "";
    int max_len = 0, start = 0;
    int center = 0, right = 0;
    vector<int> p(2 * n + 1, 0); // 对应预处理后的 p 数组

    for (int i = 0; i < 2 * n + 1; ++i) {
        // 计算原字符串的对称位置
        int mirror = 2 * center - i;
        if (i < right) {
            p[i] = min(right - i, p[mirror]);
        }

        // 计算当前预处理位置对应的原字符串左右指针
        int l = i - (p[i] + 1);
        int r = i + (p[i] + 1);

        // 映射到原字符串的索引：l' = l/2, r' = r/2 - 1
        while (l >= 0 && r < 2 * n + 1) {
            int cl = l / 2, cr = (r - 1) / 2;
            if (cl >= n || cr >= n || s[cl] != s[cr]) break;
            p[i]++;
            l--;
            r++;
        }

        // 更新 center 和 right
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        // 更新最长回文子串
        int cur_len = p[i];
        if (cur_len > max_len) {
            max_len = cur_len;
            start = (i - p[i]) / 2;
        }
    }
    return s.substr(start, max_len);
}

3.2 统计所有回文子串数量

Manacher 算法可扩展为统计所有回文子串的数量（需遍历 p 数组累加）：

// 统计所有回文子串数量（基于 Manacher）
long long count_palindromes(const string& s) {
    string t = preprocess(s);
    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    long long total = 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 (t[i + p[i] + 1] == t[i - (p[i] + 1)]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        // 累加回文子串数量：每个 p[i] 对应 floor(p[i]/2) 个回文子串
        total += p[i] / 2;
    }
    return total;
}

四、Manacher 算法的常见错误与注意事项

4.1 常见错误

预处理边界错误：未添加 ^ 和 $，导致扩展时越界访问；
半径与长度转换错误：将原字符串回文长度直接取 p[i]（正确应为 p[i]-1）；
起始位置计算错误：未除以 2，导致起始位置偏移；
对称位置逻辑错误：mirror 计算错误（正确应为 2*center - i）。

4.2 注意事项

字符集兼容：算法不依赖字符类型，可处理任意字符（包括中文、数字等）；
空字符串处理：需提前判断空字符串，避免后续逻辑出错；
性能对比：对于短字符串（n<1000），中心扩展法和 Manacher 算法效率差异不大；对于长字符串（n>10^4），Manacher 算法优势显著。

4.3 Manacher 与其他回文算法对比

算法/数据结构	时间复杂度	空间复杂度	核心优势	适用场景
Manacher 算法	O(n)	O(n)	仅找最长回文子串，实现简单	最长回文子串查询
回文自动机	O(n)	O(n)	统计所有回文子串信息	回文子串数量/出现次数统计
中心扩展法	O(n^2)	O(1)	实现极简，无需额外空间	短字符串、简单场景
后缀数组	O(n log n)	O(n)	通用，支持多字符串回文对比	多字符串最长公共回文子串

选择建议：

仅需找最长回文子串：优先用 Manacher 算法（线性时间，实现简单）；
需统计回文子串数量/出现次数：用回文自动机；
短字符串/快速实现：用中心扩展法。

五、Manacher 算法的实战应用

5.1 应用 1：判断字符串是否为回文

bool is_palindrome(const string& s) {
    string res = manacher(s);
    return res.size() == s.size();
}

5.2 应用 2：查找字符串中所有回文子串

vector<string> find_all_palindromes(const string& s) {
    string t = preprocess(s);
    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;
    vector<string> res;

    for (int i = 1; i < n - 1; ++i) {
        int mirror = 2 * center - i;
        if (i < right) p[i] = min(right - i, p[mirror]);
        while (t[i + p[i] + 1] == t[i - (p[i] + 1)]) p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        // 提取所有以 i 为中心的回文子串
        int len = p[i];
        if (len > 0) {
            int start = (i - len) / 2;
            string sub = s.substr(start, len);
            res.push_back(sub);
        }
    }
    // 去重
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

5.3 应用 3：最长回文子序列（扩展）

注意：Manacher 算法解决的是子串问题（连续字符），最长回文子序列（非连续）需用动态规划，但可结合 Manacher 优化部分场景：

// 最长回文子序列（DP 实现，对比参考）
int longestPalindromeSubseq(const string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; ++j) {
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

六、总结

Manacher 算法是解决最长回文子串问题的'最优解'，核心要点可总结为：

核心思想：通过预处理统一奇偶回文，利用回文对称性避免重复扩展，实现线性时间复杂度；
核心结构：p 数组（回文半径）、center（当前最右回文中心）、right（当前最右回文边界）；
核心步骤：预处理 → 对称初始化 → 中心扩展 → 更新边界 → 结果转换；
核心优势：线性时间/空间，实现简单，是最长回文子串问题的首选算法；
适用场景：最长回文子串查询、回文子串数量统计、字符串回文性验证等。

掌握 Manacher 算法的关键：

理解预处理的作用（统一奇偶回文）；
牢记对称位置的计算逻辑（mirror = 2*center - i）；
熟练掌握预处理后索引与原字符串索引的转换关系。

Manacher 算法是 C++ 算法竞赛中处理回文子串问题的基础算法，其'利用对称性减少重复计算'的思想，也可迁移到其他字符串算法的优化中。