Python实现最长回文子串：从中心扩展到Manacher算法优化
本文详解Python求解最长回文子串长度的两种核心方法。首先介绍基础的中心扩展法，通过插入特殊字符统一处理奇偶长度回文串。随后深入分析Manacher算法的优化思路，利用已知最大半径提前剪枝，避免无效计算。通过对比1000个字符的测试数据，展示优化后算法性能提升约10倍的实际效果，并提供完整代码实现与测试案例。
给定一个字符串，目标是计算其包含的最长回文子串的长度。例如，对于输入字符串'35534321'，其内部存在最长回文子串'3553'，因此应返回数值4。
最直观的思路是枚举所有可能的子串，并逐一验证其是否为回文串，最终返回长度最大的那个。然而，这种暴力枚举的时间复杂度极高，在实际应用中往往难以接受。为此，我们可以采用中心扩展法来高效查找。该方法选取一个字符作为中心，向两侧扩散寻找以该点为圆心的最大回文子串。但这里存在一个难点：回文子串的长度可能是奇数也可能是偶数。对于偶数长度的回文串，并不存在单一的“中心字符”。为了解决这个问题，Manacher算法提出了一种预处理策略：在原字符串中插入特殊分隔符（如'#'）。例如，原字符串'35534321'转换为'#3#5#5#3#4#3#2#1#'。经过这种变换后，无论原回文串长度奇偶，新字符串中均存在明确的中心点。此时使用中心扩展法得到的半径值，直接对应原回文子串的长度。
明确了上述思路后，具体实现步骤如下：首先将原始字符串'35534321'转换为'#3#5#5#3#4#3#2#1#'的形式，然后遍历新字符串中的每个元素，计算以该元素为中心的最长回文子串长度。以下是Python语言的具体实现代码：
#!/usr/bin/python
# -*- coding: utf-8 -*-
def max_substr(string):
s_list = [s for s in string]
string = '#' + '#'.join(s_list) + '#'
max_length = 0
length = len(string)
for index in range(0, length):
r_length = get_length(string, index)
if max_length < r_length:
max_length = r_length
return max_length
def get_length(string, index):
# 循环求出index为中心的最长回文字串
length = 0
r_ = len(string)
for i in range(1,index+1):
if index+i < r_ and string[index-i] == string[index+i]:
length += 1
else:
break
return length
if __name__ == "__main__":
result = max_substr("35534321")
print result
功能验证显示代码运行无误，但进一步思考可以发现优化空间。在当前解法中，我们计算了'35534321'中每个位置的中心最大回文长度。例如，当遍历到字符'4'时，已知当前记录的最长回文子串长度max_length为4。此时计算以'4'为中心的回文长度仅为3，小于max_length，因此无需更新max_length。这意味着之前的计算属于冗余操作。优化的核心在于：如果某个元素为中心扩展出的回文长度无法超越当前已知的max_length，则无需进行完整计算。在遍历新元素时，优先判断其潜在的最大回文范围是否可能超过max_length，若不可能，则直接跳过。以下是优化后的代码实现：
#!/usr/bin/python
# -*- coding: utf-8 -*-
def max_substr(string):
s_list = [s for s in string]
string = '#' + '#'.join(s_list) + '#'
max_length = 0
length = len(string)
for index in range(0, length):
r_length = get_length2(string, index, max_length)
if max_length < r_length:
max_length = r_length
return max_length
def get_length2(string, index, max_length):
# 基于已知的最长字串求最长字串
# 1.中心+最大半径超出字符串范围, return
r_ = len(string)
if index + max_length > r_:
return max_length
# 2.无法超越最大半径, return
l_string = string[index - max_length + 1 : index + 1]
r_string = string[index : index + max_length]
if l_string != r_string[::-1]:
return max_length
# 3.计算新的最大半径
result = max_length
for i in range(max_length, r_):
if index-i >= 0 and index+i < r_ and string[index-i] == string[index+i]:
result += 1
else:
break
return result - 1
if __name__ == "__main__":
result = max_substr("35534321")
print result
性能提升效果如何？以包含1000个字符'1'的字符串为例进行基准测试：优化前的算法执行时间为0.239018201828秒，而优化后的算法执行时间缩短至0.0180191993713秒。由此可见，优化策略使执行速度提升了约10倍。
/usr/bin/python /Users/hakuippei/PycharmProjects/untitled/the_method_of_programming.py 0.239018201828 0.0180191993713
此外，分享另一个完整的测试实例供参考：
#!usr/bin/env python
#encoding:utf-8
'''
__Author__:沂水寒城
功能：寻找最长回文子序列
'''
def slice_window(one_str,w=1):
'''
滑窗函数
'''
res_list=[]
for i in range(0,len(one_str)-w+1):
res_list.append(one_str[i:i+w])
return res_list
def is_huiwen(one_str_list):
'''
输入一个字符串列表，判断是否为回文序列
'''
if len(one_str_list)==1:
return True
else:
half=len(one_str_list)/2
if len(one_str_list)%2==0:
first_list=one_str_list[:half]
second_list=one_str_list[half:]
else:
first_list=one_str_list[:half]
second_list=one_str_list[half+1:]
if first_list==second_list[::-1]:
return True
else:
return False
def find_longest_sub_palindrome_str(one_str):
'''
主函数,寻找最长回文子序列
'''
all_sub=[]
for i in range(1,len(one_str)):
all_sub+=slice_window(one_str,i)
all_sub.append(one_str)
new_list=[]
for one in all_sub:
if is_huiwen(list(one)):
new_list.append(one)
new_list.sort(lambda x,y:cmp(len(x),len(y)),reverse=True)
print new_list[0]
if __name__ == '__main__':
one_str_list=['uabcdcbaop','abcba','dmfdkgbbfdlg','mnfkabcbadk']
for one_str in one_str_list:
find_longest_sub_palindrome_str(one_str)
该实例的运行结果如下：
abcdcba abcba bb abcba [Finished in 0.3s]
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
