请求优化字符串回文子串计数算法至O(N)时间复杂度

没问题！你当前的代码是暴力枚举所有长度≥2的子串，再逐个判断是否为回文，这种思路的时间复杂度是O(n³)（枚举子串是O(n²)，每个回文判断是O(n)），对于较长的字符串来说效率非常低。要做到O(n)的时间复杂度，咱们可以用Manacher算法——这是专门用来在线性时间内找出所有回文子串的经典算法，完美适配你的需求。

核心思路 #

Manacher算法通过以下步骤实现线性时间效率：

1. 预处理字符串：在原字符串的每个字符之间插入一个特殊字符（比如#），把所有回文统一成奇数长度的形式，避免分奇偶情况讨论（比如原字符串abba变成#a#b#b#a#）。
2. 维护回文边界：用一个数组记录每个位置为中心的最长回文半径，同时维护当前已知的最右回文边界和对应的中心，利用之前计算的信息跳过重复比较，避免不必要的字符匹配。
3. 统计有效回文：根据预处理后的字符串的回文半径，计算出原字符串中长度>1的回文子串总数。

优化后的代码 #

def count_palindromic_slices(S):
    if len(S) < 2:
        return 0
    
    # 预处理字符串，统一奇偶长度回文的处理逻辑
    processed = '#' + '#'.join(S) + '#'
    n = len(processed)
    palindrome_radius = [0] * n  # 记录每个位置为中心的最长回文半径
    current_center = 0
    current_right = 0
    total = 0
    
    for i in range(n):
        # 计算当前位置的镜像位置
        mirror = 2 * current_center - i
        
        # 利用已有的回文信息初始化当前半径，避免重复比较
        if i < current_right:
            palindrome_radius[i] = min(current_right - i, palindrome_radius[mirror])
        
        # 尝试扩展回文半径
        while (i + palindrome_radius[i] + 1 < n 
               and i - (palindrome_radius[i] + 1) >= 0 
               and processed[i + palindrome_radius[i] + 1] == processed[i - (palindrome_radius[i] + 1)]):
            palindrome_radius[i] += 1
        
        # 更新当前最右回文边界和对应的中心
        if i + palindrome_radius[i] > current_right:
            current_center = i
            current_right = i + palindrome_radius[i]
        
        # 根据当前中心类型（原字符/插入的#）计算有效贡献
        if i % 2 == 1:
            # 中心是原字符串的字符，对应奇数长度回文
            contribution = max(0, (palindrome_radius[i] - 1) // 2)
        else:
            # 中心是插入的#，对应偶数长度回文
            contribution = max(0, palindrome_radius[i] // 2)
        total += contribution
    
    return total

代码解释 #

• 预处理字符串：比如"abc"变成"#a#b#c#"，这样不管原回文是奇数还是偶数长度，都可以用同一个中心处理逻辑。
• 回文半径初始化：通过镜像位置的半径信息，避免从0开始扩展，减少重复比较。
• 扩展半径：仅在必要时扩展回文边界，每个字符最多被访问两次，保证线性时间复杂度。
• 贡献计算：区分中心类型，只统计原字符串中长度>1的回文子串，避免把单个字符的回文计入结果。

测试验证 #

比如输入"aaa"，函数返回3，对应回文子串"aa"（位置0-1）、"aa"（位置1-2）、"aaa"（位置0-2）；输入"abba"，函数返回2，对应回文子串"bb"（位置1-2）、"abba"（位置0-3），结果完全正确。

内容的提问来源于stack exchange，提问作者12345