题解 | #最长回文子串#

对于给定的长度为 n 的字符串 A，要设计一个高效算法计算其中最长回文子串的长度，可以使用马拉车（Manacher）算法，该算法的时间复杂度为 O(N)，空间复杂度也为 O(N)。

马拉车算法的基本思想是利用已知的回文信息来加速后续的回文判断。具体步骤如下：

1. 预处理： 将原字符串 A 转换为一个新的字符串 B，其中 B 的长度为 2n+1。在 A 的每个字符之间以及首尾都插入一个特殊字符（通常是一个原字符串中不会出现的字符，比如 #）。这样做的目的是将奇数长度和偶数长度的回文统一起来处理。
2. 初始化： 创建一个数组 P，其中 P[i] 表示以 B[i] 为中心的最长回文子串向左/右扩展的长度（不包括 B[i]）。初始化 P 数组中的所有元素为 0。设置两个变量，中心 C 和右边界 R，初始化为 0。
3. 遍历： 遍历字符串 B，对于每个位置 i，进行以下操作：如果 i 在当前的回文右边界 R 内，利用回文的对称性，可以快速得到一个关于 P[i] 的初步估计：P[i] = min(R - i, P[2 * C - i])。这里 2 * C - i 是 i 关于中心 C 的对称位置。以 i 为中心，尝试向两边扩展，更新 P[i]。如果以 i 为中心的回文右边界超过了当前的回文右边界 R，则更新 C 和 R 的值。
4. 结果： 遍历完成后，P 数组中的最大值就是原字符串 A 中最长回文子串的长度（对于偶数长度的回文，实际长度是 P[i] - 1）。

这样，我们就能在 O(N) 的时间复杂度和空间复杂度内计算出字符串 A 中最长回文子串的长度。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        # write code here
        t = '#' + '#'.join(A) + '#'
        n = len(t)
        P = [0] * n
        C = R = 0

        for i in range(1, n - 1):
            # 利用已知回文信息
            if R > i:
                P[i] = min(R - i, P[2 * C - i])

            # 尝试扩展回文
            while i + P[i] + 1 < n and i - P[i] - 1 >= 0 and t[i + P[i] + 1] == t[i - P[i] - 1]:
                P[i] += 1

            # 更新中心和右边界
            if i + P[i] > R:
                C, R = i, i + P[i]

            print(i, t[i], P)
        # 由于在每个字符间都插入了特殊字符，拓展长度即为原始回文串长度
        return max(P)  # 原字符串中的长度