最长回文子串算法对偶数回文正常，奇数回文处理异常求助

问题描述 #

这段Python代码用中心扩展法提取最长回文子串，能正确处理偶数长度回文，但无法正确处理奇数长度回文：

some_input_2 = "abdbaabeeba"
size_of_some_input_2 = len(some_input_2)
max = 0
final_max = 0
idx_center_letter = 0
final_idx_center_letter = 0
for j in range(2):
    for idx, letter in enumerate(some_input_2):
        i = 0
        while i <= int(size_of_some_input_2 / 2) + 1 and not idx - i < 0 and not idx + i+j >= size_of_some_input_2:
            upper_idx = idx + i +j
            bottom_idx = idx - i
            if some_input_2[bottom_idx] == some_input_2[upper_idx]:
                i = i + 1
            else:
                break
        if max < i :
            max = i #-j
            idx_center_letter = idx + 1

    if final_max <= max:
        final_max = max
        final_idx_center_letter = idx_center_letter
        print(max)
        print(idx_center_letter)
print(some_input_2[final_idx_center_letter - final_max:final_idx_center_letter + final_max])

• 输入abdbaabeeba时，错误输出偶数回文abdbaa（正确最长奇数回文是abdba）
• 输入abbaabeeba时能正确输出abeeba

错误原因分析 #

1. 半径计算未区分奇偶回文 #

中心扩展法中：

• j=0对应奇数长度回文（中心为单个字符）：循环结束后i是成功扩展的次数+1，实际有效半径是i-1（比如i=3时，实际能向外扩展2层）
• j=1对应偶数长度回文（中心为两个字符间隙）：循环结束后i就是有效扩展次数，半径为i

但代码里直接把max = i，没有根据j调整半径，导致奇数回文的半径被多算1，截取时范围错误。

2. 中心索引赋值错误 #

代码里idx_center_letter = idx +1把0索引的中心转成了1索引，但后续截取子串时用这个1索引加减半径，会导致范围偏移。比如奇数回文中心是0索引的2（字符'd'），转成1索引3后，用半径3截取会得到0到6的错误范围。

3. 外层循环未重置临时变量 #

每次j循环（切换奇偶模式）前，没有重置max和idx_center_letter，导致前一次模式的结果干扰当前模式的判断，比如偶数模式的max可能覆盖奇数模式的正确值。

4. 子串截取公式未匹配奇偶模式 #

不管奇偶，都用final_idx_center_letter - final_max : final_idx_center_letter + final_max截取，奇数回文的长度应该是2*有效半径+1，偶数是2*有效半径，统一用同一公式必然出错。

修正后的代码 #

some_input_2 = "abdbaabeeba"
size = len(some_input_2)
max_len = 0
start = 0  # 记录最长回文的起始索引

for j in range(2):
    for idx in range(size):
        i = 0
        # 扩展循环，直到越界或字符不相等
        while idx - i >= 0 and idx + i + j < size:
            if some_input_2[idx - i] == some_input_2[idx + i + j]:
                i += 1
            else:
                break
        # 计算当前回文长度和起始索引
        if j == 0:
            # 奇数长度：2*(i-1)+1 = 2i-1
            current_length = 2 * i - 1
            radius = i - 1
            current_start = idx - radius
        else:
            # 偶数长度：2*i
            current_length = 2 * i
            radius = i
            current_start = idx - radius + 1
        
        # 更新最长回文信息
        if current_length > max_len:
            max_len = current_length
            start = current_start

# 截取并输出最长回文子串
print(some_input_2[start:start + max_len])

修正后输入abdbaabeeba会正确输出abdba，输入abbaabeeba输出abeeba。

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