Python实现输入字符串多最长回文子串提取方案咨询

一、修改原动态规划代码以支持提取所有最长回文子串 #

你的原代码采用动态规划思路，但仅记录了单个最长回文的起始位置。要提取所有最长回文子串，需要调整逻辑，维护一个列表来存储所有符合最长长度的回文子串的索引信息，具体修改如下：

import sys 

def get_substring(st, low, high):
    return st[low : high + 1]

def longestPalSubstr(st):
    n = len(st)
    # table[i][j] 标记子串 st[i..j] 是否为回文
    table = [[False for _ in range(n)] for _ in range(n)]
    
    max_length = 1
    longest_pals = []
    
    # 处理长度为1的子串
    for i in range(n):
        table[i][i] = True
        longest_pals.append(get_substring(st, i, i))
    
    # 处理长度为2的子串
    for i in range(n - 1):
        if st[i] == st[i + 1]:
            table[i][i + 1] = True
            current_sub = get_substring(st, i, i + 1)
            if max_length < 2:
                max_length = 2
                longest_pals = [current_sub]
            elif max_length == 2:
                longest_pals.append(current_sub)
    
    # 处理长度大于2的子串
    k = 3
    while k <= n:
        i = 0
        while i < (n - k + 1):
            j = i + k - 1
            if table[i + 1][j - 1] and st[i] == st[j]:
                table[i][j] = True
                current_sub = get_substring(st, i, j)
                if k > max_length:
                    max_length = k
                    longest_pals = [current_sub]
                elif k == max_length:
                    longest_pals.append(current_sub)
            i += 1
        k += 1
    
    # 去重（避免重复子串）
    longest_pals = list(set(longest_pals))
    
    print("所有最长回文子串：")
    for pal in longest_pals:
        print(pal)
    print(f"最长长度：{max_length}")
    return longest_pals, max_length

# 测试代码
st = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga"
longest_pals, length = longestPalSubstr(st)

修改说明： #

• 新增get_substring函数用于获取子串，替代原printSubStr的输出逻辑，更便于收集结果
• 用longest_pals列表存储所有符合最长长度的回文子串
• 遍历过程中根据当前子串长度与max_length的关系，更新列表：
  • 发现更长的回文时，清空列表并添加新子串，更新max_length
  • 发现长度等于max_length的回文时，直接添加到列表
• 最后对列表去重，避免重复的子串（比如原字符串中多次出现的相同回文）

二、更简洁的中心扩展法实现 #

中心扩展法是寻找回文子串的常用思路，核心思想是：以每个字符（奇数长度回文的中心）或每对相邻字符（偶数长度回文的中心）为起点，向两侧扩展，直到无法形成回文为止。这种方法实现更直观，且容易收集所有最长回文子串：

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 返回当前找到的回文子串
    return s[left + 1:right]

def find_all_longest_palindromes(s):
    if not s:
        return []
    
    longest_pals = []
    max_length = 0
    
    for i in range(len(s)):
        # 奇数长度回文
        pal_odd = expand_around_center(s, i, i)
        # 偶数长度回文
        pal_even = expand_around_center(s, i, i + 1)
        
        # 处理奇数长度回文
        if len(pal_odd) > max_length:
            max_length = len(pal_odd)
            longest_pals = [pal_odd]
        elif len(pal_odd) == max_length:
            longest_pals.append(pal_odd)
        
        # 处理偶数长度回文
        if len(pal_even) > max_length:
            max_length = len(pal_even)
            longest_pals = [pal_even]
        elif len(pal_even) == max_length:
            longest_pals.append(pal_even)
    
    # 去重并返回
    return list(set(longest_pals)), max_length

# 测试代码
st = "agiaehajg32123agaajgak12345654321sasbbqwertytrewqgaga"
longest_pals, length = find_all_longest_palindromes(st)
print("所有最长回文子串：")
for pal in longest_pals:
    print(pal)
print(f"最长长度：{length}")

方法说明： #

• expand_around_center函数负责从指定中心向两侧扩展，返回找到的回文子串
• 遍历字符串中的每个位置，分别处理奇数和偶数长度的回文情况
• 同样通过维护longest_pals列表和max_length变量，收集所有最长回文子串
• 最后去重，确保结果中没有重复子串

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