CSP信奥赛新增的算法-马拉车算法（Manacher‘s Algorithm）

适合小学六年级的同学理解马拉车算法（Manacher’s Algorithm），我们会用有趣的故事和简单代码来解释。

一、故事理解：用镜子找宝藏 🔍

假设我们要在字符串中找到最长的回文（正反读都一样的字符串），比如在字符串 S = "abba" 中找最长回文：

1. 插入分隔符：把字符串变成 T = "#a#b#b#a#"

   • 作用：统一奇偶长度的回文查找
   • 就像在字符之间放镜子，方便反射观察

2. 维护三个法宝：

   • C：当前回文的中心（像灯塔）
   • R：已知回文的最右边界（像地图边界）
   • P[i]：每个位置的回文半径（记录每个点的能量）

3. 镜面反射技巧：

   • 当探测新位置i时，用C的镜像位置mirror = 2*C - i直接复制半径
   • 像用镜子快速复制已知信息，避免重复计算

二、C++代码实现 🖥️

#include <iostream>
#include <vector>
using namespace std;string longestPalindrome(string s) {if (s.empty()) return "";// 1. 插入分隔符（变成奇数长度）string T = "#";for (char c : s) {T += c;T += '#';}int n = T.size();vector<int> P(n, 0); // 每个中心的回文半径int C = 0, R = 0;    // 当前中心和右边界int maxLen = 0, center = 0;for (int i = 0; i < n; i++) {// 2. 找镜像位置，快速获得初始半径int mirror = 2 * C - i;if (i < R) {P[i] = min(R - i, P[mirror]);}// 3. 中心扩展int left = i - (P[i] + 1);int right = i + (P[i] + 1);while (left >= 0 && right < n && T[left] == T[right]) {P[i]++;left--;right++;}// 4. 更新中心和边界if (i + P[i] > R) {C = i;R = i + P[i];}// 5. 记录最大值if (P[i] > maxLen) {maxLen = P[i];center = i;}}// 转换回原字符串位置int start = (center - maxLen) / 2;return s.substr(start, maxLen);
}int main() {string s = "abba";cout << "最长回文子串：" << longestPalindrome(s) << endl;return 0;
}

三、关键步骤图解 🎨

以输入 "abba" 为例：

四、复杂度分析 ⚡

• 时间复杂度：O(n) → 比暴力法O(n²)快得多
• 空间复杂度：O(n) → 存储每个位置的半径

关键技巧：通过镜像反射避免重复计算，像用镜子复制已知信息！