python实现求最长回文子串长度 python实现求最长回文子串长度
熔遁丶螺旋手里剑 人气:0给定一个字符串,求它最长的回文子串长度,例如输入字符串'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_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]
加载全部内容