python如何實(shí)現(xiàn)求最長回文子串長度

這篇文章給大家分享的是有關(guān)python如何實(shí)現(xiàn)求最長回文子串長度的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

給定一個(gè)字符串，求它最長的回文子串長度，例如輸入字符串'35534321'，它的最長回文子串是'3553'，所以返回4。

最容易想到的辦法是枚舉出所有的子串，然后一一判斷是否為回文串，返回最長的回文子串長度。不用我說，枚舉實(shí)現(xiàn)的耗時(shí)是我們無法忍受的。那么有沒有高效查找回文子串的方法呢？答案當(dāng)然是肯定的，那就是中心擴(kuò)展法，選擇一個(gè)元素作為中心，然后向外發(fā)散的尋找以該元素為圓心的最大回文子串。但是又出現(xiàn)了新的問題，回文子串的長度即可能是基數(shù)，也可能好是偶數(shù)，對(duì)于長度為偶數(shù)的回文子串來說是不存在中心元素的。那是否有一種辦法能將奇偶長度的子串歸為一類，統(tǒng)一使用中心擴(kuò)展法呢？它就是manacher算法，在原字符串中插入特殊字符，例如插入#后原字符串變成'#3#5#5#3#4#3#2#1#'。現(xiàn)在我們對(duì)新字符串使用中心擴(kuò)展發(fā)即可，中心擴(kuò)展法得到的半徑就是子串的長度。

現(xiàn)在實(shí)現(xiàn)思路已經(jīng)明確了，先轉(zhuǎn)化字符串'35534321'  ---->  '#3#5#5#3#4#3#2#1#'，然后求出以每個(gè)元素為中心的最長回文子串的長度。以下給出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‘中每個(gè)元素中心的最大回文子串。當(dāng)遍歷到'4'時(shí)，我們已經(jīng)知道目前最長的回文子串的長度max_length是4，這是我們求出了以4為中心的最長回文子串長度是3，它比max_length要小，所以我們不更新max_length。換句話說，我們計(jì)算以4為中心的最長回文字串長度是做了無用功。這就是我們要優(yōu)化的地方，既然某個(gè)元素的最長的回文子串長度并沒有超過max_length，我們就沒有必要計(jì)算它的最長回文子串，在遍歷一個(gè)新的元素時(shí)，我們要優(yōu)先判斷以它為中心的回文子串的長度是否能超越max_length，如果不能超過，就繼續(xù)遍歷下一個(gè)元素。以下是優(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_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.計(jì)算新的最大半徑
  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個(gè)‘1'為例，優(yōu)化前的算法執(zhí)行時(shí)間為0.239018201828，優(yōu)化后為0.0180191993713，速度提升了10倍左右

/usr/bin/python /Users/hakuippei/PycharmProjects/untitled/the_method_of_programming.py
0.239018201828
0.0180191993713

再給大家分享一個(gè)實(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): 
  '''
  輸入一個(gè)字符串列表，判斷是否為回文序列 
  ''' 
  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如何實(shí)現(xiàn)求最長回文子串長度”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！