核心概述
马拉车算法（Manacher’s Algorithm）以统一奇偶中心与对称性复用为核心，在 O(n) 时间内求解字符串的最长回文子串与各中心半径。
原文引述
Description: Find all longest palindromes in O(n) using Manacher’s algorithm. Handles odd/even lengths uniformly by inserting separators. Returns radius array for each center. Time: O(n) Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景
- 目的：在一个字符串中同时处理奇回文与偶回文，线性时间得到每个中心的最大回文半径与全局最长回文。
- 思路：在字符间插入分隔符统一奇偶中心，利用已知区间 [l,r] 的对称性减少比较次数。
-
接口/字段/数据结构与输入输出语义（按仓库约定）
- 典型接口（据约定风格）：
- vector
manacher(const string& s) - 返回半径数组 d，其中 d[i] 表示在扩展串 t 中以 i 为中心的最大回文半径。
- 可选：vector<pair<int,int>> longestPalindromes(const string& s)
- 返回所有最长回文在原串中的区间。
- vector
- 输出语义：
- d 为扩展串半径；原串的奇/偶回文长度可由 d 的奇偶索引映射回推。
- 典型接口（据约定风格）：
-
核心流程与关键要点（统一处理）
- 扩展串 t：t = ’#’ + s[0] + ’#’ + s[1] + ’#’ + … + ’#’ + s[n−1] + ’#’
- |t| = 2n+1；奇数位为原字符，偶数位为分隔符。
- 维护当前最右回文 [l,r]，遍历 i=0..|t|−1：
- 初始半径 k = (i > r) ? 1 : min(d[l+r−i], r−i+1)。
- 向两侧扩展匹配，更新 d[i]、以及当 i+k−1 > r 时更新 l、r。
- 回到原串：
- 原串位置 i 的最长奇回文长度 = d[2i+1]；
- 位置 i 与 i+1 间隔的最长偶回文长度 = d[2i+2]。
- 正确性要点与不变式：
- 对称点 i’ = l + r − i 的半径已知，d[i] 至少可达到 min(d[i’], r−i+1)。
- 实现注意：
- 索引边界与字符等值比较；分隔符需保证与任何字符均不相等。
- 扩展串 t：t = ’#’ + s[0] + ’#’ + s[1] + ’#’ + … + ’#’ + s[n−1] + ’#’
-
复杂度与边界条件
- 时间 O(n)：每个中心的指针总扩展次数线性。
- 空间 O(n)：扩展串与半径数组。
- 边界：空串或单字符串时返回的半径与区间按定义退化。
-
与相邻技术的取舍对比
- 与哈希判回文：哈希可通过二分求回文长度，典型 O(n log n)，而 Manacher 线性但实现需注意细节（参见 119-字符串-字符串哈希、120-字符串-Codeforces哈希）。
- 与单模式匹配类：功能不同；若需模式匹配可参见 121-字符串-KMP、126-字符串-Z函数。
- 与后缀结构：后缀数组/树适合全局子串关系分析，复杂度与用途不同（见 124-字符串-后缀数组、125-字符串-后缀树）。