力扣刷题笔记-最长回文子串-Manacher算法求最长回文子串

[MuseAria]

Manacher算法的核心思想

算法的核心在于通过特殊字符的插入，将偶数长度和奇数长度的回文子串统一处理。具体步骤如下：

字符串预处理：在每个字符间插入一个特殊字符（通常是#），并在字符串的开始和结束位置分别插入不同的特殊字符（如$和^），以避免越界。这样，原字符串中的所有回文子串都被转换为奇数长度，便于统一处理。

初始化辅助数组：定义一个数组p[]，其中p[i]表示以字符s[i]为中心的最长回文子串向左/右扩展的长度（不包括s[i]本身）。

中心扩展：从左到右遍历处理后的字符串，对于每个位置i，根据已知的最长回文子串信息，快速确定p[i]的初始值，然后尝试向外扩展，更新p[i]。

动态维护：在遍历过程中，动态维护当前已知的最长回文子串的右边界border和中心centre。如果i + p[i]超过了border，则更新border和centre。

结果提取：遍历完成后，p[]数组中的最大值减一即为原字符串的最长回文子串长度。

力扣实战代码：
def longestPalindrome(self, s: str) -> str:
# 处理字符串，插入特殊字符来统一奇偶回文情况
t = "#" + "#".join(s) + "#"
n = len(t)
p = [0] * n # p[i] 表示以 t[i] 为中心的回文半径
center, right = 0, 0 # center 是回文中心，right 是回文的右边界
max_len, start = 0, 0 # max_len 是最长回文的半径，start 是回文的起始位置
for i in range(n):
# 对称位置
mirror = 2 * center - i

        if i < right:
            p[i] = min(right - i, p[mirror])  # 使用对称点的回文信息来初始化 p[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
        
        # 如果回文的右边界超出了 right，更新 center 和 right
        if i + p[i] > right:
            center, right = i, i + p[i]
            
        # 记录最长回文半径
        if p[i] > max_len:
            max_len = p[i]
            start = (i - p[i]) // 2  # 从 t 中恢复原字符串的起始位置
    return s[start:start + max_len]