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

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

現(xiàn)在實(shí)現(xiàn)思路已經(jīng)明確了，先轉(zhuǎn)化字符串'35534321'  ---->  '#3#5#5#3#4#3#2#1#'，然后求出以每個(gè)元素為中心的最長(zhǎng)回文子串的長(zhǎng)度。以下給出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_lengthdef get_length(string, index):  # 循環(huán)求出index為中心的最長(zhǎng)回文字串  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

功能已經(jīng)實(shí)現(xiàn)了，經(jīng)過(guò)測(cè)試也沒(méi)有bug，但是我們靜下心來(lái)想一想，目前的解法是否還有優(yōu)化空間呢？根據(jù)目前的解法，我們求出了‘35534321‘中每個(gè)元素中心的最大回文子串。當(dāng)遍歷到'4'時(shí)，我們已經(jīng)知道目前最長(zhǎng)的回文子串的長(zhǎng)度max_length是4，這是我們求出了以4為中心的最長(zhǎng)回文子串長(zhǎng)度是3，它比max_length要小，所以我們不更新max_length。換句話說(shuō)，我們計(jì)算以4為中心的最長(zhǎng)回文字串長(zhǎng)度是做了無(wú)用功。這就是我們要優(yōu)化的地方，既然某個(gè)元素的最長(zhǎng)的回文子串長(zhǎng)度并沒(méi)有超過(guò)max_length，我們就沒(méi)有必要計(jì)算它的最長(zhǎng)回文子串，在遍歷一個(gè)新的元素時(shí)，我們要優(yōu)先判斷以它為中心的回文子串的長(zhǎng)度是否能超越max_length，如果不能超過(guò)，就繼續(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_length2(string, index, max_length)    if max_length < r_length:      max_length = r_length  return max_lengthdef get_length2(string, index, max_length):  # 基于已知的最長(zhǎng)字串求最長(zhǎng)字串  # 1.中心+最大半徑超出字符串范圍, return  r_ = len(string)  if index + max_length > r_:    return max_length  # 2.無(wú)法超越最大半徑, 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 - 1if __name__ == "__main__":  result = max_substr("35534321")  print result