python实现求最长子串长度
2018-06-18 00:47:34来源：未知 阅读 ()
给定一个字符串，求它最长的回文子串长度，例如输入字符串'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
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
下一篇：Python的中文编码问题
- python3基础之“术语表（2）” 2019-08-13
- python3 之 字符串编码小结（Unicode、utf-8、gbk、gb2312等 2019-08-13
- Python3安装impala 2019-08-13
- 小白如何入门 Python 爬虫？ 2019-08-13
- python_字符串方法 2019-08-13
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
