最长回文子串（Manacher算法）

我将为您详细讲解最长回文子串问题及其高效解法——Manacher算法。

问题描述

给定一个字符串s，找到s中最长的回文子串。回文串是正着读和反着读都一样的字符串。

示例：

• 输入："babad"，输出："bab"或"aba"
• 输入："cbbd"，输出："bb"

暴力解法分析

最直观的方法是检查所有可能的子串是否为回文：

• 时间复杂度：O(n³)或O(n²)（优化后）
• 空间复杂度：O(1)

这种方法在长字符串上效率很低。

Manacher算法详解

核心思想

Manacher算法通过利用回文的对称性来避免重复计算，将时间复杂度降到O(n)。

关键概念

1. 预处理：在字符间插入特殊字符（如'#'），将奇偶长度的回文统一处理

   • 原字符串："aba" → "#a#b#a#"
   • 原字符串："abba" → "#a#b#b#a#"

2. 回文半径数组P：记录以每个位置为中心的最长回文半径

算法步骤

步骤1：字符串预处理

def preprocess(s):
    if not s:
        return "^$"
    result = "^"
    for char in s:
        result += "#" + char
    result += "#$"
    return result

预处理后字符串以'^'开头，'$'结尾，避免边界检查。

步骤2：初始化变量

• C：当前找到的最右回文的中心
• R：当前找到的最右回文边界
• P：回文半径数组
• n：预处理后字符串长度

步骤3：主循环处理
对于每个位置i（从1到n-2）：

def longestPalindrome(s):
    if not s:
        return ""
    
    # 预处理
    T = preprocess(s)
    n = len(T)
    P = [0] * n
    C, R = 0, 0
    
    for i in range(1, n-1):
        # i_mirror是i关于C的对称点
        i_mirror = 2 * C - i
        
        if R > i:
            # 利用对称性，避免重复计算
            P[i] = min(R - i, P[i_mirror])
        else:
            P[i] = 0
        
        # 尝试扩展回文
        while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1
        
        # 更新中心和右边界
        if i + P[i] > R:
            C = i
            R = i + P[i]
    
    # 找到最大回文
    max_len = 0
    center_index = 0
    for i in range(1, n-1):
        if P[i] > max_len:
            max_len = P[i]
            center_index = i
    
    # 计算原字符串中的起始位置
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

详细示例分析

以字符串"babad"为例：

预处理结果：

原始：b a b a d
处理：^ # b # a # b # a # d # $
索引：0 1 2 3 4 5 6 7 8 9 10 11 12

处理过程：

1. i=1: C=0, R=0，直接扩展，P[1]=0
2. i=2: C=2, R=2，P[2]=1（回文"#b#"）
3. i=3: 利用对称性，P[3]=0
4. i=4: 利用对称性，P[4]=3（回文"#b#a#b#"）
5. 继续处理...

最终找到最长回文半径为3，对应原字符串"bab"或"aba"。

时间复杂度分析

• 预处理：O(n)
• 主循环：每个字符最多被比较一次，O(n)
• 总时间复杂度：O(n)
• 空间复杂度：O(n)

算法优势

1. 线性时间复杂度：比动态规划的O(n²)更优
2. 统一处理：通过预处理统一处理奇偶长度回文
3. 利用对称性：避免重复计算，提高效率

完整代码实现

def longestPalindrome(s):
    def preprocess(s):
        if not s:
            return "^$"
        result = "^"
        for char in s:
            result += "#" + char
        result += "#$"
        return result
    
    T = preprocess(s)
    n = len(T)
    P = [0] * n
    C, R = 0, 0
    
    for i in range(1, n-1):
        i_mirror = 2 * C - i
        
        if R > i:
            P[i] = min(R - i, P[i_mirror])
        else:
            P[i] = 0
        
        # 扩展回文
        while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
            P[i] += 1
        
        # 更新中心和边界
        if i + P[i] > R:
            C = i
            R = i + P[i]
    
    # 寻找最大值
    max_len = 0
    center_index = 0
    for i in range(1, n-1):
        if P[i] > max_len:
            max_len = P[i]
            center_index = i
    
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

Manacher算法是解决最长回文子串问题的最优解法，在实际应用中表现出色。