給定一個字符串，求它最長的回文子串長度，例如輸入字符串'35534321'，它的最長回文子串是'3553'，所以返回4。
最容易想到的辦法是枚舉出所有的子串，然后一一判斷是否為回文串，返回最長的回文子串長度。不用我說，枚舉實現的耗時是我們無法忍受的。那么有沒有高效查找回文子串的方法呢？答案當然是肯定的，那就是中心擴展法，選擇一個元素作為中心，然后向外發散的尋找以該元素為圓心的最大回文子串。但是又出現了新的問題，回文子串的長度即可能是基數，也可能好是偶數，對于長度為偶數的回文子串來說是不存在中心元素的。那是否有一種辦法能將奇偶長度的子串歸為一類，統一使用中心擴展法呢？它就是manacher算法，在原字符串中插入特殊字符，例如插入#后原字符串變成'#3#5#5#3#4#3#2#1#'。現在我們對新字符串使用中心擴展發即可，中心擴展法得到的半徑就是子串的長度。
現在實現思路已經明確了，先轉化字符串'35534321' ----> '#3#5#5#3#4#3#2#1#'，然后求出以每個元素為中心的最長回文子串的長度。以下給出python/288113.html">python/300813.html">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_lengthdef 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 lengthif __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_lengthdef 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 - 1if __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.py0.2390182018280.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_listdef 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]
新聞熱點
疑難解答
