别再暴力匹配了！用Manacher算法5分钟搞定最长回文子串（附C++模板）

5分钟征服最长回文子串：Manacher算法实战指南

回文串判断是算法竞赛和面试中的经典问题。当面对"最长回文子串"这类题目时，很多人的第一反应是使用暴力匹配或中心扩展法。这些方法虽然直观，但时间复杂度高达O(n²)，在面对大规模数据时往往力不从心。1975年，计算机科学家Glenn Manacher提出了一种巧妙的线性时间算法，这就是我们今天要深入探讨的Manacher算法（俗称马拉车算法）。

1. 从暴力解法到Manacher的进化之路

1.1 暴力中心扩展法的局限性

中心扩展法是最直观的回文串查找方法：遍历字符串的每个字符，将其作为回文中心向两侧扩展，直到字符不匹配为止。对于偶数长度回文，还需要在字符之间虚拟中心点。

// 暴力中心扩展法示例 int expandAroundCenter(string s, int left, int right) { while (left >= 0 && right < s.size() && s[left] == s[right]) { left--; right++; } return right - left - 1; }

这种方法虽然简单，但存在明显缺陷：

• 时间复杂度高：最坏情况下需要O(n²)时间
• 重复计算：无法利用之前计算过的回文信息
• 偶数处理麻烦：需要单独处理偶数长度回文情况

1.2 Manacher算法的核心洞察

Manacher算法的精妙之处在于它充分利用了回文串的对称性质。算法维护了几个关键变量：

通过维护这些变量，算法能够：

1. 利用之前计算的回文信息减少不必要的比较
2. 统一处理奇偶长度回文
3. 保证线性时间复杂度

2. Manacher算法实现详解

2.1 预处理：统一奇偶处理

Manacher算法的第一步是对字符串进行预处理，插入特殊字符（通常用'#'）来消除奇偶差异：

原始字符串: "abba"
处理后: "#a#b#b#a#"

这种处理带来两个好处：

• 所有回文都变为奇数长度
• 边界处理更简单（首尾也添加特殊字符）

string preProcess(string s) { string result = "#"; for (char c : s) { result += c; result += '#'; } return result; }

2.2 核心算法流程

算法主体部分通过维护当前最右回文边界和其中心来优化计算：

vector<int> manacher(string s) { string t = preProcess(s); int n = t.size(); 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]; } } return p; }

2.3 关键点解析

1. 对称性利用：当当前点i在已知回文右边界内时，可以通过镜像点快速确定初始半径
2. 边界更新：每当发现更远的右边界时，更新中心和右边界
3. 线性时间保证：每个字符最多被比较一次

3. 算法优化与边界处理

3.1 实际编码中的常见陷阱

即使理解了算法原理，实现时仍可能遇到以下问题：

• 数组越界：扩展时未检查边界
• 初始值设置不当：导致不必要的比较
• 更新条件错误：中心点更新不及时

3.2 优化后的完整模板

#include <vector> #include <algorithm> using namespace std; string preProcess(const string &s) { string result = "^#"; for (char c : s) { result += c; result += '#'; } result += '$'; return result; } int longestPalindrome(string s) { string t = preProcess(s); int n = t.size(); vector<int> p(n, 0); int c = 0, r = 0, maxLen = 0; for (int i = 1; i < n-1; i++) { int mirror = 2 * c - i; p[i] = (r > i) ? min(r - i, p[mirror]) : 0; while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) { p[i]++; } if (i + p[i] > r) { c = i; r = i + p[i]; } maxLen = max(maxLen, p[i]); } return maxLen; }

这个模板添加了边界字符('^'和'$')来简化边界检查，是竞赛中的实用版本。

4. 实战应用与性能对比

4.1 算法性能实测

我们对比三种方法在不同输入规模下的表现：

从测试数据可以看出，Manacher算法在大规模数据下优势明显。

4.2 常见题目变形

Manacher算法不仅能解决基础的最长回文子串问题，还能应用于：

1. 统计所有回文子串：通过半径数组计算
2. 最长双回文串：预处理左右最大回文信息
3. 回文分割问题：结合动态规划使用

以LeetCode 5. Longest Palindromic Substring为例，使用Manacher的解决方案：

class Solution { public: string longestPalindrome(string s) { string t = "^#"; for (char c : s) { t += c; t += '#'; } t += '$'; int n = t.size(); vector<int> p(n, 0); int c = 0, r = 0; int maxCenter = 0, maxLen = 0; for (int i = 1; i < n-1; i++) { int mirror = 2 * c - i; p[i] = (r > i) ? min(r - i, p[mirror]) : 0; while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) { p[i]++; } if (i + p[i] > r) { c = i; r = i + p[i]; } if (p[i] > maxLen) { maxLen = p[i]; maxCenter = i; } } int start = (maxCenter - maxLen) / 2; return s.substr(start, maxLen); } };

这个实现不仅找到了最长回文子串的长度，还能返回具体的子串内容。

5. 算法扩展与高级应用

5.1 处理更复杂的回文问题

Manacher算法可以扩展解决一些变种问题：

• 回文分割：结合动态规划
• 回文对计数：与其他字符串算法结合
• 周期性回文：分析回文半径的模式

5.2 与其他算法的结合

在实际问题中，Manacher常与其他算法协同工作：

1. 后缀自动机：处理更复杂的字符串匹配
2. 哈希算法：快速比较子串
3. 动态规划：解决最优分割问题

例如，解决"将字符串分割为最少回文子串"问题时，可以结合Manacher和动态规划：

int minCut(string s) { int n = s.size(); vector<int> cut(n+1, 0); for (int i = 0; i <= n; i++) { cut[i] = i-1; } vector<int> p = manacher(s); for (int i = 0; i < 2*n+1; i++) { if (p[i] > 0) { int center = i / 2; int radius = p[i]; int start = center - (radius - 1) / 2; int end = center + radius / 2; for (int j = end; j >= start; j--) { cut[j+1] = min(cut[j+1], cut[start] + 1); } } } return cut[n]; }

这种组合方案比纯动态规划解法效率更高。