0x00.引入
回文子串是字符串问题中的经典考点，而寻找字符串中最长回文子串更是高频题型。在 Manacher 算法出现之前，常规的暴力枚举中心 + 扩展方法时间复杂度为 O (n²)，对于长字符串（如长度 1e6 的文本）难以满足效率要求。Manacher 算法作为一种线性时间复杂度（O (n)）的解决方案，凭借其巧妙的优化思路，成功将这类问题的求解效率提升到最优水平，如今已成为算法竞赛和工程实践中的必备技能。
本文将从算法原理、核心步骤、代码实现到实战应用，全面拆解 Manacher 算法，帮助读者快速掌握这一高效工具。
0x01.核心辅助装：字符串预处理
回文子串分为奇数长度（如 "aba"，中心为单个字符）和偶数长度（如 "abba"，中心为两个字符之间的空隙），直接处理需分两种情况讨论，逻辑繁琐。
预处理方案
在原字符串的开头、结尾以及每两个字符之间插入一个原串中不存在的特殊字符（如 '#'）。例如：
原串："abcba" → 处理后："#a#b#c#b#a#"
原串："abba" → 处理后："#a#b#b#a#"
那么这样预处理有什么优势呢？
所有回文子串的长度均变为奇数，统一了中心类型（均为单个字符，如处理后 "#a#b#b#a#" 的回文中心为中间的 '#'）；
处理后回文子串的半径与原串长度存在明确对应关系：设处理后回文子串的半径为 r（以中心为基准，向左右各扩展 r-1 个字符），则原串中对应回文子串的长度为 r-1。例如：
处理后 "#a#b#c#b#a#" 的最长回文子串半径为 6 → 原串长度 6-1=5（√）；
处理后 "#a#b#b#a#" 的最长回文子串半径为 5 → 原串长度 5-1=4（√）。
比较关键的定义
数组 d [i]：表示以处理后字符串 s [i] 为中心的最长回文子串的半径（即从中心向左右各扩展 d [i]-1 个字符，包含中心在内的回文子串长度为 2*d [i]-1）；
变量 mid：当前已找到的所有回文子串中，右端点最靠右的回文子串的中心位置；
变量 r：当前已找到的所有回文子串中，右端点的最大值（即该回文子串的右边界为 r）。
0x02优化
遍历处理后的字符串时，对于当前位置 i，利用之前已计算的 d 数组信息，避免重复扩展：
当 \(i ≤ r\) 时：i 在 mid 对应的回文子串范围内，根据回文的对称性，i 关于 mid 的对称点为 j = 2*mid - i。此时 d [i] 的初始值可由 d [j] 推导，无需从头扩展：
若 \(d [j] ≤ r - i\)：说明 j 对应的回文子串完全在 mid 的回文子串内部，根据对称性，d [i] = d [j]；
若 \(d [j] > r - i\)：说明 j 对应的回文子串部分超出 mid 的回文子串范围，d [i] 的初始值为 r - i + 1（最大可能不超出 r 的范围）；
当 i > r 时：当前位置超出所有已处理回文子串的范围，无对称信息可用，d [i] 初始值设为 1（仅包含自身）。
0x03.算法步骤
初始化：d 数组全为 0，mid=0，r=-1（初始无有效回文子串）；
遍历处理后的字符串 s（索引 i 从 0 到 n-1）：
a. 计算 d [i] 的初始值：根据 i 与 r 的位置关系，按上述规则赋值；
b. 暴力扩展：在不越界的前提下，持续判断 s [i-k] 与 s [i+k] 是否相等（k 从当前 d [i] 开始），相等则 d [i]++；
c. 更新 mid 和 r：若当前回文子串的右端点（i + d [i] - 1）大于 r，则更新 mid=i，r=i + d [i] - 1；
遍历结束后，d 数组的最大值减 1 即为原串的最长回文子串长度。
0x04.时间复杂度
看似存在暴力扩展步骤，但由于 r 在算法运行过程中严格单调递增（每次扩展后 r 只会变大，不会缩小），且每个字符最多被访问两次（一次被包含在某个回文子串中，一次作为扩展边界），因此整个算法的时间复杂度为 \(O (n)\)，其中 n 为处理后字符串的长度（约为原串长度的 2 倍）。
0x05.来点小题
1.板子（洛谷 P3805）
题目描述
给定一个只由小写英文字符组成的字符串，求其最长回文子串的长度。
代码实现
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;const int N = 2.2e7 + 10; // 适配原串长度1e7的情况
int d[N]; // 存储每个中心的回文半径int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s = "#"; // 预处理后的字符串，起始插入#char c;while ((c = getchar()) >= 'a' && c <= 'z') {s += c;s += '#'; // 字符后插入#，避免使用s = s + c + '#'（效率极低）}int n = s.size();int mid = 0, r = -1; // 当前最右回文的中心和右边界int ans = 0; // 记录最大半径for (int i = 0; i < n; ++i) {// 计算d[i]的初始值int k = (i <= r) ? min(d[2 * mid - i], r - i + 1) : 1;// 暴力扩展while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {k++;}d[i] = k--; // 扩展结束后，k多增了1，需回退// 更新mid和rif (i + k > r) {r = i + k;mid = i;}// 更新最大半径ans = max(ans, d[i]);}cout << ans - 1 << endl; // 原串最长回文长度 = 最大半径 - 1return 0;
}
2.洛谷 P1659 [国家集训队] 拉拉队排练
题目描述
给定长度为 n 的字符串 s 和 k，求 s 中所有回文串的长度中前 k 大的乘积模 19930726 的值；若回文串数量不足 k 个，输出 - 1。
解题思路
用 Manacher 算法计算所有回文子串的长度（处理后 d [i] 对应的原串长度为 d [i]-1，且仅保留奇数长度，因偶数长度已被预处理为奇数）；
用桶数组 t 统计每个长度的回文串数量（t [len] 表示长度为 len 的回文串个数）；
从最大长度到最小长度枚举，用快速幂计算前 k 大长度的乘积（若某长度的回文串个数超过剩余 k，仅取 k 个；否则取全部，k 减去该个数）。
运行
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;#define int long long
const int N = 1e6 + 10;
const int mod = 19930726;
int d[N], t[N]; // t[len]记录长度为len的回文串个数// 快速幂：计算a^b mod mod
int qpow(int a, int b) {int ans = 1;while (b) {if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}signed main() {int n, k;cin >> n >> k;string s;cin >> s;// Manacher算法预处理字符串（直接在原串上处理，无需额外插入#，因只需长度）int mid = 0, r = -1;for (int i = 0; i < n; ++i) {int k_val = (i <= r) ? min(d[2 * mid - i], r - i + 1) : 1;while (i - k_val >= 0 && i + k_val < n && s[i - k_val] == s[i + k_val]) {k_val++;}d[i] = k_val--;int len = 2 * d[i] - 1; // 原串中回文子串长度（奇数）t[len]++;if (i + k_val > r) {r = i + k_val;mid = i;}}int sum = 0, ans = 1;// 从最大可能长度（n，奇数）向下枚举for (int i = (n % 2 == 1) ? n : n - 1; i >= 1; i -= 2) {if (t[i] == 0) continue;if (sum + t[i] <= k) {// 该长度的所有回文串都计入乘积ans = ans * qpow(i, t[i]) % mod;sum += t[i];} else {// 仅取剩余k个ans = ans * qpow(i, k) % mod;sum += k;break;}}cout << (sum >= k ? ans : -1) << endl;return 0;
}
3.洛谷 P4555 [国家集训队] 最长双回文串
题目描述
给定长度为 n 的串 s，求最长双回文子串 T，即 T 可分为两部分 A 和 B（A、B 非空），且 A 和 B 均为回文串。
解题思路
预处理字符串（插入 #），用 Manacher 算法计算 d 数组；
维护两个辅助数组：
ld [i]：以处理后字符串 s [i] 为左端点的最长回文子串的半径；
rd [i]：以处理后字符串 s [i] 为右端点的最长回文子串的半径；
遍历所有可能的分割点 i（需为 #，保证 A 和 B 在原串中为整数长度），若 ld [i] 和 rd [i] 均非 0，则 A 的长度为 ld [i]，B 的长度为 rd [i]，总长度为 ld [i]+rd [i]，取最大值。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;const int N = 2e5 + 10;
int d[N], ld[N], rd[N]; // ld[i]：以i为左端点的最长回文半径；rd[i]：以i为右端点的最长回文半径int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s = "#";char c;while ((c = getchar()) >= 'a' && c <= 'z') {s += c;s += '#';}int n = s.size();int mid = 0, r = -1, ans = 0;for (int i = 0; i < n; ++i) {int k = (i <= r) ? min(d[2 * mid - i], r - i + 1) : 1;while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) {k++;}d[i] = k--;// 更新ld和rd：当前回文串的左端点为i-k，右端点为i+kld[i - k] = max(ld[i - k], k);rd[i + k] = max(rd[i + k], k);// 更新mid和rif (i + k > r) {r = i + k;mid = i;}}// 递推完善ld：向左扩展时，回文半径最多减少2（跳过两个字符）for (int i = 2; i < n; i += 2) {ld[i] = max(ld[i], ld[i - 2] - 2);}// 递推完善rd：向右扩展时，回文半径最多减少2for (int i = n - 3; i >= 0; i -= 2) {rd[i] = max(rd[i], rd[i + 2] - 2);}// 枚举分割点（必须是#，即i为偶数）for (int i = 0; i < n; ++i) {if (ld[i] && rd[i]) {ans = max(ans, ld[i] + rd[i]);}}cout << ans << endl;return 0;
}
注意事项与优化技巧
特殊字符选择：需确保插入的特殊字符（如 '#'）不在原串中出现，否则会破坏回文判断的正确性；
空间优化：对于超长字符串（如长度 1e7），可直接在原串上处理（无需额外存储处理后的字符串），通过数学计算模拟扩展过程，节省空间；
边界处理：扩展时需严格判断 i-k >= 0 和 i+k < n，避免数组越界；
效率优化：输入输出优先使用getchar()和putchar()，避免cin/cout的同步开销。
总结
Manacher 算法的核心在于利用回文的对称性减少重复计算，通过预处理统一回文类型，再结合 mid 和 r 的动态更新，实现了线性时间复杂度的求解。掌握该算法后，不仅能高效解决最长回文子串问题，还能应对各类回文相关的拓展题型（如双回文、回文长度统计等）。
建议先理解基础模板的逻辑，再通过拓展题目巩固思路，逐步掌握算法的灵活运用。多做练习（如本文提到的洛谷题目），才能真正吃透这一高效工具，在实际场景中快速应用。