Manacher算法

Manacher算法是一种用于在O(n)时间复杂度内找到字符串中最长回文子串的算法。它的高效性使其在处理大规模数据时非常有用。

算法思想

预处理字符串：在字符串的每个字符之间插入一个特殊字符（如#），并在字符串的开头和结尾也插入特殊字符。这可以避免处理奇偶长度回文的不同情况。例如，字符串"abba"会被转换为"#a#b#b#a#"。
使用辅助数组：创建一个数组P，其中P[i]表示以位置i为中心的最长回文子串的半径（包括中心）。
中心扩展法：遍历预处理后的字符串，使用中心扩展法来更新数组P。同时维护一个当前已知的最右回文边界R及其中心C。如果当前索引i在R的范围内，可以利用对称性来加速计算。
更新最优解：在遍历过程中，持续更新最长回文子串的长度和起始位置。

详细步骤

预处理：将字符串S转换为T，例如S = "abba"，则T = "^#a#b#b#a#$"。^和$是哨兵字符，防止越界。
初始化：创建数组P，长度与T相同，初始值为0。设置C = 0和R = 0。
遍历字符串：
- 对于每个位置i，如果i < R，则P[i] = min(R - i, P[2*C - i])。
- 尝试扩展以i为中心的回文子串，更新P[i]。
- 如果i + P[i] > R，则更新C = i和R = i + P[i]。
找到最长回文子串：遍历数组P，找到最大值P[i]，对应的回文子串起始位置为(i - P[i]) / 2。

代码示例

以下是Manacher算法的Python实现：

def longest_palindrome(s: str) -> str:
    # 预处理字符串
    T = '#'.join(f'^{s}$')
    n = len(T)
    P = [0] * n
    C = R = 0

    for i in range(1, n - 1):
        if i < R:
            P[i] = min(R - i, P[2 * C - i])
        
        # 尝试扩展回文
        while T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1
        
        # 更新C和R
        if i + P[i] > R:
            C, R = i, i + P[i]

    # 找到最大回文
    max_len, center_index = max((n, i) for i, n in enumerate(P))
    start = (center_index - max_len) // 2
    return s[start:start + max_len]

总结

Manacher算法通过巧妙的预处理和对称性利用，实现了在O(n)时间复杂度内找到最长回文子串。它的效率和简洁性使其成为处理回文问题的经典算法之一。希望这篇介绍能帮助你更好地理解和应用Manacher算法！

算法思想

详细步骤

代码示例

相关LeetCode题目

总结