python實(shí)現(xiàn)求最長回文子串長度
給定一個字符串，求它最長的回文子串長度，例如輸入字符串'35534321'，它的最長回文子串是'3553'，所以返回4。
最容易想到的辦法是枚舉出所有的子串，然后一一判斷是否為回文串，返回最長的回文子串長度。不用我說，枚舉實(shí)現(xiàn)的耗時是我們無法忍受的。那么有沒有高效查找回文子串的方法呢？答案當(dāng)然是肯定的，那就是中心擴(kuò)展法，選擇一個元素作為中心，然后向外發(fā)散的尋找以該元素為圓心的最大回文子串。但是又出現(xiàn)了新的問題，回文子串的長度即可能是基數(shù)，也可能好是偶數(shù)，對于長度為偶數(shù)的回文子串來說是不存在中心元素的。那是否有一種辦法能將奇偶長度的子串歸為一類，統(tǒng)一使用中心擴(kuò)展法呢？它就是manacher算法，在原字符串中插入特殊字符，例如插入#后原字符串變成'#3#5#5#3#4#3#2#1#'?，F(xiàn)在我們對新字符串使用中心擴(kuò)展發(fā)即可，中心擴(kuò)展法得到的半徑就是子串的長度。
現(xiàn)在實(shí)現(xiàn)思路已經(jīng)明確了，先轉(zhuǎn)化字符串'35534321' ----> '#3#5#5#3#4#3#2#1#'，然后求出以每個元素為中心的最長回文子串的長度。以下給出python實(shí)現(xiàn):
#!/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):
# 循環(huán)求出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
功能已經(jīng)實(shí)現(xiàn)了，經(jīng)過測試也沒有bug，但是我們靜下心來想一想，目前的解法是否還有優(yōu)化空間呢？根據(jù)目前的解法，我們求出了‘35534321‘中每個元素中心的最大回文子串。當(dāng)遍歷到'4'時，我們已經(jīng)知道目前最長的回文子串的長度max_length是4，這是我們求出了以4為中心的最長回文子串長度是3，它比max_length要小，所以我們不更新max_length。換句話說，我們計算以4為中心的最長回文字串長度是做了無用功。這就是我們要優(yōu)化的地方，既然某個元素的最長的回文子串長度并沒有超過max_length，我們就沒有必要計算它的最長回文子串，在遍歷一個新的元素時，我們要優(yōu)先判斷以它為中心的回文子串的長度是否能超越max_length，如果不能超過，就繼續(xù)遍歷下一個元素。以下是優(yōu)化后的實(shí)現(xiàn)：
#!/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'為例，優(yōu)化前的算法執(zhí)行時間為0.239018201828，優(yōu)化后為0.0180191993713，速度提升了10倍左右
/usr/bin/python /Users/hakuippei/PycharmProjects/untitled/the_method_of_programming.py 0.239018201828 0.0180191993713
再給大家分享一個實(shí)例：
#!usr/bin/env python
#encoding:utf-8
'''
__Author__:沂水寒城
功能：尋找最長回文子序列
'''
def slice_window(one_str,w=1):
'''
滑窗函數(shù)
'''
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):
'''
主函數(shù),尋找最長回文子序列
'''
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)
結(jié)果如下：
abcdcba abcba bb abcba [Finished in 0.3s]
相關(guān)文章
這篇文章主要介紹了Python 序列的方法總結(jié)的相關(guān)資料,需要的朋友可以參考下2016-10-10
這篇文章主要介紹了python獲取mp3文件信息的方法,涉及Python針對文件屬性操作的相關(guān)技巧,需要的朋友可以參考下2015-06-06
Python中使用正則表達(dá)式及正則表達(dá)式匹配規(guī)則詳解
這篇文章主要介紹了Python中使用正則表達(dá)式以及正則表達(dá)式匹配規(guī)則,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-03-03
使用pyinstaller打包PySide2程序中遇到的問題
說到打包，我們就需要用到python程序的打包工具pyinstaller了,這個包安裝簡單,使用同樣簡單,下面這篇文章主要給大家介紹了關(guān)于使用pyinstaller打包PySide2程序中遇到的問題,需要的朋友可以參考下2023-05-05
Matplotlib是一款極其強(qiáng)大的Python數(shù)據(jù)可視化庫，這篇文章中，我們將深入討論 Matplotlib 的一些高級特性，包括對象導(dǎo)向接口、自定義顏色映射和樣式、動態(tài)圖形等，感興趣的小伙伴跟著小編一起來探討吧2023-07-07
jmeter執(zhí)行python腳本的實(shí)現(xiàn)示例
本文主要介紹了jmeter執(zhí)行python腳本的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要介紹了python 獲取剪切板內(nèi)容的兩種方法，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-11-11
如何基于opencv實(shí)現(xiàn)簡單的數(shù)字識別
現(xiàn)在很多場景需要使用的數(shù)字識別,比如銀行卡識別,以及車牌識別等,在AI領(lǐng)域有很多圖像識別算法,大多是居于opencv 或者谷歌開源的tesseract 識別,下面這篇文章主要給大家介紹了關(guān)于如何基于opencv實(shí)現(xiàn)簡單的數(shù)字識別,需要的朋友可以參考下2021-09-09
Python 正則表達(dá)式中re.group()使用小結(jié)
正則表達(dá)式是在處理字符串時非常有用的工具,而re.group()是在匹配到的文本中提取特定分組內(nèi)容的方法之一,這篇文章主要介紹了Python 正則表達(dá)式之re.group()用法,需要的朋友可以參考下2024-01-01
本文主要介紹了django中path和url函數(shù)的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03