Manacher算法（最长回文子串） 题目描述 给定一个字符串，求其最长回文子串（Longest Palindromic Substring）。例如，字符串 "babad" 的最长回文子串为 "bab" 或 "aba"。要求算法的时间复杂度优化至 O(n)。 1. 问题分析 暴力解法需要枚举所有子串（O(n²)）并检查是否回文（O(n)），总复杂度 O(n³)。优化后可通过中心扩展法（从每个字符或间隙向两侧扩展）将复杂度降至 O(n²)。但 Manacher 算法能进一步优化到 O(n)，核心思想是 利用回文的对称性避免重复计算 。 2. 预处理：统一奇偶长度回文 在原字符串的每个字符间插入特殊字符（如 # ），使所有回文子串长度变为奇数。 示例： 原字符串 "aba" → "#a#b#a#" （新长度恒为奇数）。 边界加入不同字符（如 ^ 和 $ ）避免越界检查。 3. 核心概念与符号定义 回文半径数组 p[i] ：以新字符串第 i 个字符为中心的回文半径（含自身）。 例如： # a # b # a # 下标 0 1 2 3 4 5 6 p[3] = 4 （回文 #a#b#a# 半径覆盖到边界）。 中心 C 与右边界 R ：当前已知回文的最右边界 R 及其对应的中心 C 。 4. 算法步骤详解 遍历新字符串的每个位置 i ，计算 p[i] ： 情况1： i 在已知回文右边界 R 的左侧 找到 i 关于中心 C 的对称点 j = 2*C - i 。 若 j 的回文半径 p[j] 未超过 C 的左边界（即 p[j] < R - i ），则直接令 p[i] = p[j] 。 原理 ：因 [C-R, C+R] 是回文， j 与 i 对称， j 的回文在 C 的回文范围内时， i 的回文必然相同。 若 p[j] ≥ R - i ，则先令 p[i] = R - i ，再继续向外扩展。 情况2： i 在 R 右侧 无法利用对称性，直接以 i 为中心扩展，同时更新 C = i ， R = i + p[i] 。 扩展操作 比较 i ± p[i] 的字符是否相同，若相同则 p[i]++ ，直到不同。 5. 示例演示 以字符串 "babad" 为例： 预处理后： ^#b#a#b#a#d#$ （忽略边界符细节）。 遍历过程简析： i=1 ：中心 b ， R 从 0 更新到 2， C=1 。 i=2 ：对称点 j=0 ， p[0]=0 ，扩展得 p[2]=1 。 i=3 ：对称点 j=1 ， p[1]=1 ，但 i+p[j]=4 未超 R=2 ，故 p[3]=p[1]=1 ，然后扩展发现 #b#a#b# 回文，更新 p[3]=4 ， C=3 ， R=7 。 最终最大 p[i] 对应回文子串为 #a#b#a# 或 #b#a#b# ，去掉 # 得 "aba" 或 "bab" 。 6. 复杂度与正确性 时间复杂度 O(n) ：每个字符最多被扩展一次， R 随遍历单调递增。 空间复杂度 O(n) ：存储预处理字符串和 p 数组。 7. 关键总结 预处理解决奇偶性问题。 利用 p 数组和 (C, R) 避免重复扩展。 实际代码需注意边界处理与最终结果转换（ 最长长度 = max(p[i]) - 1 ）。 通过此算法，可在线性时间内高效解决最长回文子串问题。