Manacher算法：线性时间求解最长回文子串 问题描述 最长回文子串问题要求在一个给定的字符串中找出最长的连续回文子串。回文串是指正着读和反着读都一样的字符串，例如"aba"、"abba"都是回文串。暴力解法的时间复杂度为O(n³)，而Manacher算法能够在O(n)时间内解决这个问题。 算法核心思想 Manacher算法通过利用回文串的对称性来避免重复计算。算法首先对原始字符串进行预处理，插入特殊字符（如#）将奇偶长度的回文串统一为奇数长度处理。 详细步骤 1. 字符串预处理 在原始字符串的每个字符之间和首尾插入一个特殊字符（通常用#） 例如：字符串"abba"预处理后变为"#a#b#b#a#" 预处理后字符串长度总是奇数，避免了奇偶长度回文串的区别处理 2. 核心概念定义 P[ i ]：表示以位置i为中心的最长回文半径（包含中心） C：当前找到的右边界最靠右的回文串的中心位置 R：当前找到的右边界最靠右的回文串的右边界位置 3. 算法流程 初始化C=0，R=0，然后从左到右遍历预处理后的字符串： 对于每个位置i： 如果i在R的左侧（i ≤ R）： 利用对称性，i关于C的对称点j = 2C - i P[ i]的初始值取min(R - i, P[ j ]) 这是因为： 如果j处的回文完全在C处回文的左半部分，则P[ i] = P[ j ] 如果j处的回文超出C处回文的左边界，则P[ i ] = R - i 如果i在R的右侧（i > R）： P[ i ]的初始值设为1（至少自身是回文） 中心扩展： 以i为中心，向左右两侧扩展，比较S[ i + P[ i]]和S[ i - P[ i] ] 如果相等，P[ i ]增加1，继续扩展 直到字符不相等或到达字符串边界 更新C和R： 如果i + P[ i ] - 1 > R（即当前回文右边界超过已知右边界） 更新C = i，R = i + P[ i ] - 1 4. 示例演示 以字符串"babad"为例： 预处理后："#b#a#b#a#d#" 遍历过程： i=0: P[ 0 ]=1, C=0, R=0 i=1: 扩展后P[ 1 ]=2, 更新C=1, R=2 i=2: 利用对称性，P[ 2]初始值=min(2, P[ 0])=1，扩展后P[ 2 ]=4 ...（继续计算所有位置） 5. 结果提取 找到P数组中的最大值max_ len和其索引center 原始字符串中的起始位置：(center - max_ len) / 2 长度：max_ len - 1 算法复杂度分析 时间复杂度：O(n)，每个字符最多被比较一次 空间复杂度：O(n)，用于存储P数组和预处理字符串 关键优化点 对称性利用：通过维护当前最右回文边界，避免重复计算 预处理统一：将奇偶长度回文串统一处理 避免暴力扩展：通过已知信息减少不必要的字符比较 Manacher算法是处理回文相关问题的经典算法，在实际工程中有广泛应用。