寻找所有回文子串：能否线性时间解决？最优算法是什么？

能否在线性时间内找出所有回文子串？ #

答案是否定的。因为回文子串的数量最多可达**O(n²)**级别（例如全相同字符的字符串"aaaaa"，回文子串总数为n*(n-1)/2），仅输出所有结果就需要O(n²)的时间，因此不可能做到线性时间输出所有回文子串。

不过，如果仅统计回文子串的数量或者找到最长回文子串，Manacher算法可以做到**O(n)**的线性时间复杂度，但输出所有子串的步骤仍需O(n²)时间。

最优算法选择 #

1. Manacher算法（核心处理O(n)时间） #

这是当前查找回文子串的最优算法，核心思路是通过预处理字符串统一奇偶长度回文的处理逻辑，再利用回文的对称性减少重复计算：

• 预处理：在字符串的每个字符之间插入特殊字符（如#），例如"abba"转为"#a#b#b#a#"，这样所有回文都变成以某个字符为中心的奇长度回文。
• 维护数组p：p[i]表示预处理后字符串中以第i位为中心的最长回文半径。
• 维护当前最右回文边界R和对应中心C，利用对称性直接推导部分位置的p值，避免暴力扩展，将时间复杂度压缩到O(n)。

2. 中心扩展法（实现简单，O(n²)时间） #

如果对实现复杂度要求更高，中心扩展法是更实用的选择，时间复杂度为O(n²)，远优于你当前的O(n³)代码：

• 枚举所有可能的回文中心：每个字符作为奇长度回文的中心，每两个相邻字符作为偶长度回文的中心。
• 对每个中心向左右扩展，直到字符不匹配为止，记录所有符合条件的回文子串。

以下是中心扩展法的Python实现（适配你需求中长度≥3的回文子串）：

string = input().strip()
n = len(string)

# 输出1-based索引的回文子串范围
for center in range(n):
    # 处理奇长度回文
    left, right = center, center
    while left >= 0 and right < n and string[left] == string[right]:
        if right - left + 1 >= 3:
            print(left + 1, right + 1)
        left -= 1
        right += 1
    
    # 处理偶长度回文（仅当中心不是最后一个字符时）
    if center < n - 1:
        left, right = center, center + 1
        while left >= 0 and right < n and string[left] == string[right]:
            if right - left + 1 >= 3:
                print(left + 1, right + 1)
            left -= 1
            right += 1

原代码的问题 #

你当前的代码枚举所有子串（O(n²)个），每个子串判断是否回文需要O(n)时间，总复杂度O(n³)，效率极低。中心扩展法通过减少重复判断，将时间复杂度降至O(n²)，而Manacher算法则进一步优化核心处理为线性时间。

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