求解最长回文子串：马拉车(manacher)算法详解

马拉车算法（Manacher's Algorithm）是一种用于查找字符串中最长回文子串的线性时间复杂度算法。其核心思想是通过利用回文串的对称性来避免重复高桐计算，从而将时间复杂度从O(n2)降低到O(n)。

• 预处理字符串：在原字符串的每个字符之间以及首尾插入特殊字符（如#），将字符串长度统一为奇数。例如，字符串babcbabcba会被转换为#b#a#b#c#b#a#b#c#b#a#x。

• 初始化数组：创建一个与预处理后字符串等长的数组p，用于存储每个字符的“对称半径”（不包含自身）。例如，p[0]=0，p[1]=1，p[2]=0。

• 核心变量：

  c：当前已知的最右回文子串的中心。

  mx：当前已知的最右回文子串的右边界，即mx = c + p[c]。

  max_id和max_radius：记录最大对称半径及其索引。

• 算法步骤：

  遍历字符串：对于每个字符s[i]，根据其与当前中心c的对称点j = 2 * c - i的关系，确定p[i]的值。

  三种情况处理：

  情况1：如果j - p[j] > 2 * c - mx，说明s[j]的对称半径在c的对称范围内，因此p[i] = p[j]。

  情况2：如果j - p[j] < 2 * c - mx，说明s[j]的对称半径超出c的对称范围，因此p[i] = mx - i。

  情况3：如果j - p[j] == 2 * c - mx，说明s[j]的对称半径正好在庆念握c的对称边界上，此时需要使用中心展开法进一步计算p[i]。

  更新中心和边界：如果i + p[i] > mx，则更新中心c和边界mx。

  记录最大值：如果p[i]大于当前记录的max_radius，则更新max_id和max_radius。

• 中心展开法：用于处理无法直接利用对称性的情况，即从当前字符向左右扩展，直到字符不匹配为止。

• 结果提取：根据max_id和max_radius从预处理后的字符串中提取最长回文子串，并去除插入的特殊字符。

• 代码实现：

  def longestPalindrome(self, s: str) -> str: if len(s) < 2: return s s = '#' + '#'.join(list(s)) + '#' p = [0 for x in range(len(s))] max_id = -1 max_radius = -1 c = -1 mx = -1 for i in range(len(s)): if i > mx: radius = getExpandLength(i, i, s) // 2 p[i] = radius c = i mx = i + radius if radius > max_radius: max_id, max_radius = i, radius else: j = 2*c - i if j - p[j] > 2 * c - mx: p[i] = p[j] elif j - p[j] < 2 * c - mx: p[i] = mx - i else: radius = getExpandLength(i-p[j]-1, i+p[j]+1, s) // 2 p[i] = radius if i + radius > mx: c = i mx = i + radius if radius > max_radius: max_id, max_radius = i, radius return s[max_id-max_radius:max_id+max_radius+1].replace('#', '')

• 时间复杂度：O(n)，其中n是字誉庆符串的长度。

• 空间复杂度：O(n)，用于存储预处理后的字符串和数组p。

通过上述步骤，马拉车算法高效地找到了字符串中的最长回文子串，避免了重复计算，显著提高了算法的效率。