如何用Python高效统计字符串中所有回文子串的数目？

Question

如何优化Python代码以高效统计字符串中的所有回文子串数目？给定一个字符串，暴力解法通过检查每个可能的子串是否为回文，时间复杂度高达O(n^3)，效率低下。而使用中心扩展算法可以将时间复杂度降低到O(n^2)。但当字符串长度较大时，性能仍可能不足。此时，Manacher算法是一个更优的选择，它通过记录和利用已计算的回文半径，将时间复杂度降至线性O(n)。然而，在实际应用中，如何正确实现Manacher算法并处理不同字符间的特殊分隔符（如“#”），以及如何适配偶数长度回文子串的统计，是常见的技术难点。此外，还需注意Python中字符串切片和列表操作的开销，避免不必要的内存消耗。如何在这些方法之间权衡并选择最适合场景的算法？

Answer 1

1. 问题背景与暴力解法

在字符串处理领域，统计所有回文子串数目是一个经典的算法问题。暴力解法通过枚举所有可能的子串并逐一判断是否为回文，时间复杂度高达O(n^3)。这种方法虽然简单易懂，但在实际应用中效率低下，尤其是在字符串长度较大时。

以下是暴力解法的Python实现：

def count_palindromic_substrings_brute(s):
    n = len(s)
    count = 0
    for i in range(n):
        for j in range(i, n):
            if s[i:j+1] == s[i:j+1][::-1]:
                count += 1
    return count

尽管暴力解法易于理解，但其性能瓶颈显而易见。为了优化性能，我们需要引入更高效的算法。

2. 中心扩展算法及其优化

中心扩展算法的核心思想是以每个字符（或两个字符之间）为中心，向两侧扩展以寻找最长回文子串。该算法的时间复杂度为O(n^2)，相比暴力解法有显著提升。

以下是中心扩展算法的Python实现：

def count_palindromic_substrings_center(s):
    n = len(s)
    count = 0
    for center in range(2 * n - 1):
        left = center // 2
        right = left + center % 2
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    return count

中心扩展算法避免了不必要的字符串切片操作，减少了内存消耗。然而，当字符串长度进一步增大时，O(n^2)的时间复杂度仍然可能成为瓶颈。

3. Manacher算法详解

Manacher算法是一种线性时间复杂度（O(n)）的高效算法，用于解决最长回文子串问题。它通过引入特殊分隔符（如“#”）将原字符串转换为奇数长度字符串，并记录和利用已计算的回文半径来加速计算。

以下是Manacher算法的关键步骤：

1. 对原始字符串进行预处理，插入分隔符。
2. 初始化辅助数组P，用于存储每个位置的最大回文半径。
3. 利用中心扩展的思想，结合已知回文半径信息加速计算。

以下是Manacher算法的Python实现：

def preprocess(s):
    return '#'.join('^{}$'.format(s))

def count_palindromic_substrings_manacher(s):
    T = preprocess(s)
    n = len(T)
    P = [0] * n
    C = R = 0
    for i in range(1, n-1):
        mirr = 2 * C - i
        if R > i:
            P[i] = min(R - i, P[mirr])
        while T[i + (1 + P[i])] == T[i - (1 + P[i])]:
            P[i] += 1
        if i + P[i] > R:
            C, R = i, i + P[i]
    return sum((v + 1) // 2 for v in P)

4. 算法选择与权衡

在实际应用中，选择合适的算法需要考虑以下因素：

算法	时间复杂度	空间复杂度	适用场景
暴力解法	O(n^3)	O(1)	短字符串或教学用途
中心扩展算法	O(n^2)	O(1)	中等长度字符串
Manacher算法	O(n)	O(n)	长字符串或高性能需求

此外，还需注意Python中字符串切片和列表操作的开销。尽量减少不必要的中间变量和临时对象创建，以降低内存消耗。

5. 实现流程图

以下是Manacher算法的实现流程图：

graph TD;
    A[输入字符串s] --> B{字符串长度};
    B --"长度<=1"--> C[返回0];
    B --"长度>1"--> D[预处理字符串];
    D --> E[初始化辅助数组P];
    E --> F[遍历每个字符];
    F --> G{当前字符是否在右边界内?};
    G --"是"--> H[利用镜像信息];
    G --"否"--> I[直接扩展];
    H --> J[扩展回文半径];
    I --> J;
    J --> K[更新中心和右边界];
    K --> L[累加回文子串数量];
    L --> M[返回结果];