Manacher算法是唯一O(n)求最长回文子串的通用算法，通过维护最右回文边界和对称点避免重复计算；预处理必须插入分隔符（如'#'）并加不同哨兵（如'^'、'$'）以统一处理奇偶回文。
Manacher算法为什么比暴力和中心扩展快？
因为它是唯一能 O(n) 解决最长回文子串的通用算法——不是靠剪枝或平均情况优化，而是通过维护「已知最右回文边界」和「对称点」，把大部分字符的回文半径直接继承或限制，避免重复计算。
暴力是 O(n³)（枚举所有子串+校验），中心扩展最坏仍是 O(n²)（每个中心都扩到边界）。Manacher在预处理后，每个字符最多被“真正扩展”一次，其余靠查表或镜像推导。
预处理字符串时必须插入分隔符吗？
必须。原始字符串如 "abba" 有偶数长度回文，但中心扩展法默认以字符为轴，无法自然处理偶回文；Manacher靠统一奇数化解决这个问题。
标准做法是用同一非字母符号（如 '#'）填充所有间隙，并在首尾加不同哨兵（如 '^' 和 '$'），得到形如 "^#a#b#b#a#$" 的串。这样每个回文中心严格落在一个位置，半径含义统一：回文长度 = radius - 1。
立即学习“C++免费学习笔记（深入）”；
常见错误：
• 忘记首尾哨兵 → 边界越界或循环不终止
• 用空格或 0 替代 '#' → 若原串含该字符，破坏对称性
• 哨兵相同（如都用 '$'）→ 可能导致 while 循环越界比较
manacher() 函数里三个关键变量怎么联动？
核心是维护 center、right 和 radius[] 数组。其中：
• center 是当前已知最右回文的中心索引
• right 是该回文最右位置（开区间或闭区间需统一，推荐闭区间）
• radius[i] 表示以 i 为中心的最大回文半径（含中心）
对每个新位置 i：
• 若 i ，先设 <code>radius[i] = min(radius[2 * center - i], right - i)（镜像点 + 边界截断）
• 然后尝试暴力扩展：while (s[i + radius[i]] == s[i - radius[i]]) radius[i]++
• 若 i + radius[i] - 1 > right，就更新 center = i 和 right = i + radius[i] - 1
容易踩的坑：
• 比较字符时没检查数组边界 → 越界读取（哨兵就是干这个的，但代码里仍要写 while 条件）
• 更新 right 时用了 radius[i] 而不是 radius[i] - 1 → 边界算错一格
• 把 radius[i] 直接当原串长度用 → 实际原串最长回文长度是 max_radius - 1
从 radius[] 提取原串下标要注意什么？
预处理串长为 2 * n + 3，其中有效字符位置都是奇数索引（1,3,5,...）。若在预处理串中找到最大 radius[i]，对应原串起始位置是 (i - radius[i]) / 2，长度是 radius[i] - 1。
示例：
原串 "abba" → 预处理串 "^#a#b#b#a#$"（索引 0~10）
最大回文中心在索引 5（即 'b' 后的 '#'），radius[5] = 5
则原串起始下标 = (5 - 5) / 2 = 0，长度 = 5 - 1 = 4 → 正确
关键细节：
• 中心落在 '#' 上 → 对应偶数长度回文
• 中心落在字母上 → 对应奇数长度回文
• 不要硬编码除以 2，要用整数除法，且确保 i 是奇数索引（预处理保证了这点）
边界情况容易被忽略：空串、单字符、全相同字符——这些情况下 radius 数组仍有定义，但提取逻辑不能假设一定存在非哨兵中心。
