Manacher算法（最长回文子串） Manacher算法是一种用于在字符串中查找最长回文子串的高效算法，其时间复杂度为O(n)，空间复杂度为O(n)。与动态规划方法相比，它通过利用回文的对称性避免了重复计算。 1. 问题描述与预处理 问题：给定一个字符串s，找出其最长的回文子串。 挑战：暴力解法需要O(n³)时间（枚举所有子串并检查），动态规划需要O(n²)时间和空间。 关键思路：将原字符串转换为加入分隔符的新字符串，统一处理奇偶长度回文。 例如：原字符串"aba"转换为"#a#b#a#"，原字符串"abba"转换为"#a#b#b#a#"。 预处理后，所有回文子串都变为奇数长度，且原回文中心对应新字符串的某个位置。 2. 核心概念定义 转换字符串T：在原始字符串每个字符前后插入特殊字符（如#），并在首尾加入不同字符（如^和$）避免边界检查。 示例：s = "abba" → T = "^#a#b#b#a#$" 回文半径数组P：P[ i]表示以T[ i ]为中心的最长回文子串的半径长度（包含中心）。 示例：T = "^#a#b#b#a#$"，以第二个'#'为中心的回文半径为2（对应"#a#"）。 中心C与右边界R：当前已知回文子串的中心位置和右边界位置（R为回文串最后一个字符索引+1）。 3. 算法步骤详解 算法从左到右遍历转换后的字符串T，利用对称性避免重复计算： 初始化 ： 创建数组P，长度与T相同，初始值全0。 设置当前中心C=0，右边界R=0。 遍历每个位置i ： 如果i在当前右边界R之内，利用对称性： 计算i关于中心C的对称点j = 2* C - i。 P[ i]的初始值取min(R - i, P[ j ])，避免超出已知回文区域。 如果i在R之外，P[ i ]初始值为0。 中心扩展：从i + P[ i] + 1和i - P[ i] - 1开始向两侧扩展，比较字符是否相等，更新P[ i ]。 如果i + P[ i] > R，更新C = i和R = i + P[ i ]。 查找最大值 ： 遍历P数组，找到最大值P[ maxIndex ]。 原字符串中最长回文子串的起始位置为(maxIndex - P[ maxIndex]) / 2，长度为P[ maxIndex ]。 4. 示例演示 以s = "babad"为例： 预处理：T = "^#b#a#b#a#d#$" 遍历过程（简化）： i=1: 中心为'#'，P[ 1 ]=1，C=1，R=2 i=2: 对称点j=0（'^'），P[ 2]=0，扩展后P[ 2 ]=1，更新C=2，R=3 i=3: j=1，P[ 3]=min(3-3, P[ 1])=0，扩展后P[ 3 ]=3（对应"#a#b#a#"），更新C=3，R=6 继续遍历至结束，最大P[ i ]=3，对应原字符串回文"aba"或"bab"。 5. 时间复杂度分析 每个字符最多被比较一次（R随i单调递增），因此时间复杂度为O(n)。 空间复杂度为O(n)（存储转换字符串和P数组）。 6. 实际应用 生物信息学中DNA序列的回文结构识别。 文本处理中的敏感词检测或对称模式匹配。 数据压缩和加密算法中的回文特性利用。 通过Manacher算法，我们能够高效解决最长回文子串问题，其核心在于预处理和对称性利用，避免了动态规划中的重复计算。