python实现求最长回⽂⼦串长度
给定⼀个字符串，求它最长的回⽂⼦串长度，例如输⼊字符串'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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。