python如何实现求最长回文子串长度

这篇文章给大家分享的是有关python如何实现求最长回文子串长度的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

给定一个字符串，求它最长的回文子串长度，例如输入字符串'35534321'，它的最长回文子串是'3553'，所以返回4。

最容易想到的办法是枚举出所有的子串，然后一一判断是否为回文串，返回最长的回文子串长度。不用我说，枚举实现的耗时是我们无法忍受的。那么有没有高效查找回文子串的方法呢？答案当然是肯定的，那就是中心扩展法，选择一个元素作为中心，然后向外发散的寻找以该元素为圆心的最大回文子串。但是又出现了新的问题，回文子串的长度即可能是基数，也可能好是偶数，对于长度为偶数的回文子串来说是不存在中心元素的。那是否有一种办法能将奇偶长度的子串归为一类，统一使用中心扩展法呢？它就是manacher算法，在原字符串中插入特殊字符，例如插入#后原字符串变成'#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

功能已经实现了，经过测试也没有bug，但是我们静下心来想一想，目前的解法是否还有优化空间呢？根据目前的解法，我们求出了‘35534321‘中每个元素中心的最大回文子串。当遍历到'4'时，我们已经知道目前最长的回文子串的长度max_length是4，这是我们求出了以4为中心的最长回文子串长度是3，它比max_length要小，所以我们不更新max_length。换句话说，我们计算以4为中心的最长回文字串长度是做了无用功。这就是我们要优化的地方，既然某个元素的最长的回文子串长度并没有超过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_length3(string, index, max_length)     if max_length < r_length:       max_length = r_length   return max_length def get_length3(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]

感谢各位的阅读！关于“python如何实现求最长回文子串长度”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！