字符串中所有回文子串的高效查找：Manacher算法详解

本教程详细介绍了如何高效查找字符串中的所有回文子串。针对朴素的o(n^3)算法效率瓶颈，我们引入并深入讲解了manacher算法。该算法通过巧妙的预处理和对称性利用，能够在o(n)线性时间内完成所有回文子串的识别与提取，显著提升处理大规模字符串的性能。

问题概述与朴素解法

在字符串处理中，查找所有回文子串是一个常见且重要的问题。回文子串是指一个字符串从前往后读和从后往前读都相同的子序列。例如，在字符串 "ababa" 中，回文子串包括 "aba" (索引 1-3), "bab" (索引 2-4), "aba" (索引 3-5), 和 "ababa" (索引 1-5)。

一个直观但效率不高的解决方案是遍历所有可能的子串，然后逐一检查它们是否为回文。这种方法通常需要三层循环：外层两个循环确定子串的起始和结束位置，内层一个循环或切片操作检查子串的回文性。

以下是一个使用Python实现的朴素 O(n^3) 算法示例：

def find_all_palindromic_substrings_naive(s):
    n = len(s)
    palindromes = []
    for i in range(n):
        for j in range(i, n): # j 是子串的结束索引
            sub = s[i : j+1]
            if sub == sub[::-1]:
                palindromes.append((sub, i+1, j+1)) # 存储子串及其1-based索引
    return palindromes

# 示例
s = "ababa"
result = find_all_palindromic_substrings_naive(s)
for p, start, end in result:
    print(f'"{p}" (索引 {start} 到 {end})')

# 输出:
# "a" (索引 1 到 1)
# "b" (索引 2 到 2)
# "a" (索引 3 到 3)
# "b" (索引 4 到 4)
# "a" (索引 5 到 5)
# "aba" (索引 1 到 3)
# "bab" (索引 2 到 4)
# "aba" (索引 3 到 5)
# "ababa" (索引 1 到 5)

上述代码中，外层两个循环的复杂度为 O(n^2)，而 sub == sub[::-1] 的字符串切片和比较操作在最坏情况下需要 O(n) 时间，因此总时间复杂度为 O(n^3)。对于较长的字符串，这种方法将变得非常缓慢。

Manacher算法：线性时间解决方案

为了克服 O(n^3) 算法的效率瓶颈，我们可以采用 Manacher（马拉车）算法。Manacher算法是一种专门用于在 O(n) 线性时间内查找字符串中最长回文子串的算法，但通过稍作修改，它也可以高效地识别并提取所有回文子串。其核心思想在于：

1. 预处理字符串：统一处理奇数长度和偶数长度的回文串。
2. 中心扩展法：以每个字符为中心向两边扩展，寻找回文。
3. 利用对称性：避免重复计算，利用已经找到的回文信息加速查找。

Manacher算法详解

Manacher算法的关键在于巧妙地处理字符串，使其能够统一地以每个字符（或字符之间的空隙）为中心进行扩展，并且能够利用回文的对称性来跳过一些不必要的比较。

1. 字符串预处理

原始字符串中的回文子串可能具有奇数长度（如 "aba"）或偶数长度（如 "abba"）。Manacher算法通过在原始字符串的每个字符之间以及字符串的首尾插入一个特殊字符（例如 '#'），将所有回文子串都转换为奇数长度的回文。

例如，字符串 "aba" 预处理后变为 "#a#b#a#"。 字符串 "abba" 预处理后变为 "#a#b#b#a#"。

为了避免边界检查，我们通常还会额外在处理后的字符串首尾添加不同的哨兵字符，例如 ^ 和 $。

原始字符串 s -> 预处理后的字符串 Ts = "ababa"T = "$#a#b#a#b#a#^" (这里使用 $ 和 ^ 作为哨兵)

算家云

高效、便捷的人工智能算力服务平台

37

查看详情

2. 初始化

我们需要一个 P 数组，其长度与预处理后的字符串 T 相同。P[i] 存储的是以 T[i] 为中心的最长回文子串的“半径”（即从中心到一侧的字符数，不包括中心本身）。 例如，如果 T[i] 是中心，P[i] = k 意味着以 T[i] 为中心的回文子串是 T[i-k ... i+k]。

此外，我们还需要两个变量：

• C (Center)：当前已知最长回文子串的中心索引。
• R (Right boundary)：当前已知最长回文子串的右边界，即 C + P[C]。

初始时，C = 0, R = 0 (或者根据哨兵字符的实际位置初始化)。

3. 遍历与扩展

我们从索引 i = 1 遍历到 len(T) - 2 (跳过哨兵字符)。对于每个 i：

1. 计算镜像索引 i_mirror：i_mirror = 2 * C - i。这是 i 相对于 C 的对称点。
2. 利用对称性初始化 P[i]： 如果 i < R，这意味着 i 位于当前最长回文子串 T[C-P[C] ... C+P[C]] 的内部。 此时，P[i] 的最小值可以由其镜像点 P[i_mirror] 确定，或者由 R - i 确定（因为不能超出当前最长回文的右边界）。 所以，P[i] = min(P[i_mirror], R - i)。 如果 i >= R，则 i 在当前最长回文子串之外或在其边界上，此时无法利用对称性，P[i] 初始为 0。
3. 中心扩展： 在确定 P[i] 的初始值后，我们以 T[i] 为中心，尝试向两边扩展，直到遇到不匹配的字符或到达字符串边界。 while T[i + P[i] + 1] == T[i - P[i] - 1]: P[i] += 1
4. 更新 C 和 R： 如果 i + P[i] > R，说明我们找到了一个更靠右的回文子串，此时需要更新 C = i 和 R = i + P[i]。

4. 提取所有回文子串

Manacher算法在 P 数组中存储了以 T[i] 为中心的最大回文半径。通过这个信息，我们可以提取出所有原始字符串中的回文子串。

对于 T 中的每个索引 i，如果 P[i] > 0：

• 以 T[i] 为中心，半径为 P[i] 的回文子串为 T[i-P[i] ... i+P[i]]。
• 这个回文子串的长度是 2 * P[i] + 1 (在预处理字符串中)。
• 在预处理字符串中，每隔一个 # 字符，对应原始字符串的一个字符。因此，P[i] 实际上表示了原始字符串中回文子串的“半长”或“半径”。
• 原始字符串中的起始索引：(i - P[i]) // 2
• 原始字符串中的结束索引：(i + P[i]) // 2 - 1
• 原始子串长度：P[i]

Manacher算法实现示例 (Python)

以下是使用Manacher算法查找所有回文子串的Python实现。

def manacher_find_all_palindromes(s):
    # 1. 预处理字符串
    # 例如 "ababa" -> "$#a#b#a#b#a#^"
    T = ['$', '#']
    for char in s:
        T.append(char)
        T.append('#')
    T.append('^')
    n_T = len(T)

    P = [0] * n_T  # P[i] 存储以 T[i] 为中心的回文半径
    C = 0          # 当前最长回文的中心
    R = 0          # 当前最长回文的右边界

    all_palindromes = set() # 使用集合避免重复添加相同的回文子串

    for i in range(1, n_T - 1): # 遍历 T，跳过首尾哨兵
        # 2. 利用对称性初始化 P[i]
        # i_mirror 是 i 关于 C 的对称点
        i_mirror = 2 * C - i 

        if R > i:
            # 如果 i 在当前最长回文的右边界 R 内部
            # P[i] 至少是 P[i_mirror] 和 R-i 中的较小值
            P[i] = min(R - i, P[i_mirror])
        else:
            # 如果 i 在 R 之外或与 R 重合，无法利用对称性，P[i] 从 0 开始
            P[i] = 0

        # 3. 中心扩展
        # 尝试扩展 T[i] 为中心的回文
        # T[i + P[i] + 1] 是 i 右侧的下一个字符
        # T[i - P[i] - 1] 是 i 左侧的下一个字符
        while T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1

        # 4. 更新 C 和 R
        # 如果当前回文的右边界超过了 R，则更新 C 和 R
        if i + P[i] > R:
            C = i
            R = i + P[i]

        # 5. 提取所有回文子串
        # 对于每个中心 i，P[i] 表示了以 T[i] 为中心的回文半径
        # 这个回文在 T 中的范围是 T[i - P[i] : i + P[i] + 1]
        # 原始字符串中的长度是 P[i]
        # 原始字符串中的起始索引是 (i - P[i]) // 2
        # 原始字符串中的结束索引是 (i + P[i]) // 2 - 1

        # 注意：P[i] 代表的是在预处理字符串中，从中心到一侧的#或字符的个数
        # 对于原始字符串，P[i] 的值就是回文子串的长度
        # 比如 #a#b#a#，中心是 'b' (T[3])，P[3]=2，对应原始串 "aba"，长度为3
        # 实际提取时，需要根据 P[i] 的值，从 T 中构造出子串，并去除 '#'

        # 遍历所有可能的半径，从1到P[i]，提取所有以T[i]为中心的回文
        for radius in range(1, P[i] + 1):
            # T[i - radius] 到 T[i + radius] 是一个回文
            # 提取原始子串：跳过 '#' 字符
            start_index_in_T = i - radius
            end_index_in_T = i + radius

            # 原始字符串中的子串
            original_sub = ""
            for k in range(start_index_in_T, end_index_in_T + 1):
                if T[k] != '#':
                    original_sub += T[k]

            if original_sub: # 确保不是空字符串 (比如当radius=0时，如果允许)
                all_palindromes.add(original_sub)

    return sorted(list(all_palindromes), key=len) # 按长度排序，方便查看

# 示例
s = "ababa"
palindromes = manacher_find_all_palindromes(s)
print(f"字符串 '{s}' 中的所有回文子串:")
for p in palindromes:
    print(f'"{p}"')

# 输出:
# 字符串 'ababa' 中的所有回文子串:
# "a"
# "b"
# "aba"
# "bab"
# "ababa"

s2 = "racecar"
palindromes2 = manacher_find_all_palindromes(s2)
print(f"\n字符串 '{s2}' 中的所有回文子串:")
for p in palindromes2:
    print(f'"{p}"')

# 输出:
# 字符串 'racecar' 中的所有回文子串:
# "a"
# "c"
# "e"
# "r"
# "aca"
# "cec"
# "racecar"

s3 = "google"
palindromes3 = manacher_find_all_palindromes(s3)
print(f"\n字符串 '{s3}' 中的所有回文子串:")
for p in palindromes3:
    print(f'"{p}"')

# 输出:
# 字符串 'google' 中的所有回文子串:
# "e"
# "g"
# "l"
# "o"
# "oo"
# "goog"

代码解释：

• T 数组的构建：通过在原始字符之间插入 #，并在两端添加 $ 和 ^，使得所有回文子串的长度在 T 中都变为奇数，并且简化边界处理。
• P 数组：P[i] 存储的是以 T[i] 为中心，向两边扩展的最大回文半径。例如，如果 T[i] 是 #a#b#a# 中的 b，P[i] 为 2，表示 b 左右各扩展两个字符 (#a 和 a#)，形成 T[i-2...i+2]，对应原始字符串的 aba。
• C 和 R：C 记录当前已发现的最长回文子串的中心，R 记录其右边界。这两个变量是 Manacher 算法实现 O(n) 复杂度的关键，它们帮助算法利用对称性，避免重复计算。
• i_mirror = 2 * C - i：计算当前索引 i 相对于 C 的镜像点。
• min(R - i, P[i_mirror])：这是利用对称性的核心。如果 i 在当前最长回文的范围内（即 i < R），那么 P[i] 至少可以从其镜像点 P[i_mirror] 得到，或者受限于 R 的边界。
• 提取所有回文：在遍历过程中，对于每个 i 和其对应的 P[i] 值，我们知道以 T[i] 为中心，存在半径从 1 到 P[i] 的所有回文。通过循环 radius 并从 T 中提取对应子串，然后去除 # 即可得到原始回文子串。使用 set 可以自动去重。

复杂度分析

• 时间复杂度：Manacher算法的时间复杂度为 O(n)，其中 n 是原始字符串的长度。
  • 预处理字符串需要 O(n) 时间。
  • 主循环遍历 T 数组（长度约为 2n+3）一次，每次迭代中，中心扩展的 while 循环虽然看起来是内循环，但 R 变量是单调递增的。每个字符只会被 while 循环访问和比较常数次，因此总的扩展操作也是 O(n)。
• 空间复杂度：Manacher算法的空间复杂度为 O(n)。
  • T 数组的长度约为 2n+3。
  • P 数组的长度也约为 2n+3。
  • 存储所有回文子串的集合在最坏情况下（例如字符串全部由相同字符组成 "aaaaa"）可能存储 O(n^2) 个子串，但如果只存储唯一的子串，则取决于具体内容。在我们的实现中，all_palindromes 集合存储的是去重后的回文子串，其大小最大为 O(n^2)，但如果只考虑算法本身的辅助空间，则是 O(n)。

注意事项与总结

• 预处理的重要性：Manacher算法的巧妙之处在于预处理。通过插入特殊字符，它将奇数长度和偶数长度的回文统一处理，简化了逻辑。
• 对称性与动态规划：算法通过维护 C 和 R，利用已计算的回文信息来推断新回文的最小半径，这体现了动态规划的思想，有效避免了重复计算。
• 提取所有回文：虽然Manacher算法最初是为了找到最长回文，但通过遍历 P 数组，我们可以轻松地提取出所有以每个 T[i] 为中心的回文，从而得到原始字符串中的所有回文子串。
• 适用场景：Manacher算法是处理字符串回文子串问题的最优解之一，尤其适用于需要高效处理大规模字符串或对性能有严格要求的场景。

Manacher算法提供了一种优雅且高效的方式来解决查找所有回文子串的问题，其线性时间复杂度使其在实际应用

以上就是字符串中所有回文子串的高效查找：Manacher算法详解的详细内容，更多请关注php中文网其它相关文章！