最长回文子串（Manacher算法） 题目描述： 给定一个字符串s，找到s中最长的回文子串。回文串是正着读和反着读都一样的字符串。 解题过程： 问题分析 回文串分为奇数和偶数长度两种情况： 奇数长度："aba" - 中心是字符'b' 偶数长度："abba" - 中心在两个'b'之间 传统动态规划解法需要O(n²)时间复杂度和空间复杂度。Manacher算法可以在O(n)时间内解决。 算法预处理 首先对字符串进行预处理，插入特殊字符（如'#'）来统一处理奇偶情况： 原字符串："abba" → 处理后："#a#b#b#a#" 这样所有回文子串都变成了奇数长度。 核心概念定义 定义数组p[ i ]表示以i为中心的最长回文半径（包括中心） 定义： C：当前找到的最右回文子串的中心 R：当前找到的最右回文子串的右边界 算法步骤 遍历每个位置i，计算p[ i ]： 如果i在R的右侧，则从i向两边扩展 如果i在R的左侧，则利用对称性： j = 2* C - i（i关于C的对称点） 分三种情况： a) 如果p[ j] < R-i：p[ i] = p[ j ] b) 如果p[ j] >= R-i：p[ i ]至少为R-i，然后继续扩展 c) 如果i+p[ j]正好等于R：p[ i ]至少为R-i，然后继续扩展 具体示例 以字符串"babad"为例： 预处理后："#b#a#b#a#d#" i: 0 1 2 3 4 5 6 7 8 9 10 字符: # b # a # b # a # d # p[ i ]: 1 2 1 4 1 4 1 2 1 2 1 计算过程： i=0: p[ 0 ]=1, C=0, R=0 i=1: 在R右侧，扩展得p[ 1 ]=2, C=1, R=2 i=2: 对称点j=0, p[ 2 ]=1, C=1, R=2 i=3: 对称点j=1, p[ 3]至少为1，扩展得p[ 3 ]=4, C=3, R=6 依此类推... 结果提取 最长回文半径-1就是原字符串中的回文长度。 最大p[ i ]-1就是最长回文子串长度。 时间复杂度分析 每个位置最多被扩展一次，算法时间复杂度为O(n)。 这个算法巧妙地利用了回文串的对称性质，避免了重复计算，是线性动态规划在字符串处理中的经典应用。