Python找回文子串的方法-Python教程-PHP中文网

Python找回文子串的方法

舞姬之光

发布： 2025-11-05 22:33:02

原创

384人浏览过

回文子串是正反读相同的连续子串，常用中心扩展法在O(n²)时间内找出最长回文子串；也可通过动态规划或Manacher算法优化处理。

python找回文子串的方法

判断和找回文子串是字符串处理中的常见问题。回文子串指的是正着读和反着读都一样的连续子串，比如 "aba" 或 "abba"。在 Python 中有几种有效的方法可以找出一个字符串中所有的回文子串，或者最长的回文子串。

1. 中心扩展法

回文串的特征是以某个位置或两个位置之间的空隙为中心，向两边对称扩展。我们可以枚举每个可能的中心点，然后向左右扩展，判断是否构成回文。

这种方法的时间复杂度为 O(n²)，空间复杂度为 O(1)，适合找最长回文子串。

立即学习“Python免费学习笔记（深入）”；

def longest_palindrome(s):
    if not s:
        return ""
<pre class='brush:python;toolbar:false;'>start = 0
max_len = 1

def expand_around_center(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 返回长度（注意边界）
    return right - left - 1

for i in range(len(s)):
    len1 = expand_around_center(i, i)     # 奇数长度回文
    len2 = expand_around_center(i, i+1)   # 偶数长度回文
    current_max = max(len1, len2)

    if current_max > max_len:
        max_len = current_max
        start = i - (current_max - 1) // 2

return s[start:start + max_len]

登录后复制

调用示例：

print(longest_palindrome("babad"))  # 输出："bab" 或 "aba"
print(longest_palindrome("cbbd"))   # 输出："bb"

登录后复制

2. 找出所有回文子串

如果目标是找出字符串中所有的回文子串，可以在中心扩展的基础上稍作修改，收集每一个找到的回文串。

立即学习“Python免费学习笔记（深入）”；

def find_all_palindromes(s):
    palindromes = set()  # 使用集合避免重复
<pre class='brush:python;toolbar:false;'>def expand_and_add(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        palindromes.add(s[left:right+1])
        left -= 1
        right += 1

for i in range(len(s)):
    expand_and_add(i, i)      # 奇数长度
    expand_and_add(i, i+1)    # 偶数长度

return list(palindromes)

登录后复制

示例：

AIBox 一站式AI创作平台

AIBox365一站式AI创作平台，支持ChatGPT、GPT4、Claue3、Gemini、Midjourney等国内外大模型

217

查看详情

print(find_all_palindromes("aabbaa"))
# 输出可能包含："a", "b", "aa", "bb", "abba", "aabbaa" 等

登录后复制

3. 动态规划方法

也可以使用动态规划来解决最长回文子串问题。定义 dp[i][j] 表示从索引 i 到 j 的子串是否为回文。

状态转移方程：

如果 s[i] == s[j]，且内部子串 dp[i+1][j-1] 是回文，或者子串长度 ≤ 2，则 dp[i][j] = True

时间复杂度 O(n²)，空间复杂度 O(n²)。

立即学习“Python免费学习笔记（深入）”；

def longest_palindrome_dp(s):
    n = len(s)
    if n == 0:
        return ""
<pre class='brush:python;toolbar:false;'>dp = [[False] * n for _ in range(n)]
start = 0
max_len = 1

# 单个字符都是回文
for i in range(n):
    dp[i][i] = True

# 检查长度为2的子串
for i in range(n - 1):
    if s[i] == s[i+1]:
        dp[i][i+1] = True
        start = i
        max_len = 2

# 检查长度大于2的子串
for length in range(3, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        if s[i] == s[j] and dp[i+1][j-1]:
            dp[i][j] = True
            start = i
            max_len = length

return s[start:start + max_len]

登录后复制