Manacher算法必须预处理字符串，因原串奇偶回文中心语义不同，插入'#'及边界符'^','$'可统一为奇长度回文，避免越界与漏判；预处理后长度为2n+3，radius[i]映射原串需用center=(i-1)/2、len=radius[i]-1等公式。
Manacher算法为什么必须预处理字符串
不加哨兵字符直接跑Manacher，大概率越界或漏判奇偶回文。核心原因：原串中奇数长度回文（如"aba"）和偶数长度（如"abba"）中心位置语义不同，算法靠统一“以每个位置为中心扩展”来线性推进，必须让所有回文都变成奇数长度。
标准做法是插入分隔符（如'#'），首尾再加不同边界符（如'^'和'$'），把"abba"变成"^#a#b#b#a#$"。这样每个回文中心严格落在一个字符上，且半径计算直接对应原串长度。
- 别用空格或
'0'当分隔符——可能和原数据冲突 -
'^'和'$'必须可区分且不在原串中出现，否则while扩展时会穿出边界 - 预处理后长度变为
2 * n + 3，数组开小了会Segmentation fault
radius数组怎么映射回原串的起止下标
Manacher返回的radius[i]是预处理串中以i为中心的回文半径（含中心），要转成原串下标，得先定位中心在原串的位置，再算左右边界。
假设预处理串为s_new，原串为s，s_new[i] == '#'说明该中心对应原串两个字符之间（偶回文），否则是原串某个字符（奇回文）。通用公式：
立即学习“C++免费学习笔记（深入）”；
int center = (i - 1) / 2; // 原串中心下标（向下取整） int len = radius[i] - 1; // 原串回文长度 int left = center - (len - 1) / 2; int right = center + len / 2;
- 注意整数除法截断——
(len-1)/2和len/2合起来才覆盖全长 - 如果只要最长回文，不用存所有
left/right，只记最大len和对应center即可 - 很多实现漏掉
-1，导致len算大1，下标越界
边界检查为什么不能只靠s_new[j] == s_new[k]
常见错误写法：while (s_new[j] == s_new[k]) { j--; k++; radius[i]++; }——这会在j或k越界后继续访问非法内存，触发std::out_of_range或静默崩溃。
正确逻辑必须先保界，再比字符。预处理串首尾的'^'和'$'就是干这个的：它们互不相等，且不会出现在中间，所以只要把循环条件写成while (s_new[j] == s_new[k])，就隐含了j > 0 && k ——因为两端哨兵一碰就停。
- 如果没加
'^'/'$'，必须显式写while (j >= 0 && k - 但显式判断每次多两次比较，破坏了理论上的线性性能（常数变大）
- 有些同学用
try/catch捕获异常——C++里这不是合法做法，operator[]不抛异常
C++实现里vector<int></int>初始化大小容易错在哪
预处理串长度是2 * n + 3，但radius数组必须覆盖全部索引0到2*n+2，所以vector大小至少是2 * n + 3。少开1个就会让radius[2*n+2]越界写入。
更隐蔽的坑：有人用radius.assign(2*n+3, 0)，但忘了n是int，当n很大时2*n+3可能溢出，变成负数，assign直接崩溃。
- 安全写法：
size_t len_new = s.size() * 2 + 3;，然后用vector<int>(len_new, 0)</int> - 如果输入
s为空，n=0，仍需分配3个元素——"^#$"本身就有3字符 - 别依赖
radius.reserve()，它不初始化值，未赋值区域是随机数，会影响后续max_element结果
实际写的时候，最常卡住的不是算法逻辑，而是预处理串和radius索引之间的两次转换——一次在构造时，一次在解析时。这两个地方的偏移量差1，就全乱了。
