python实现求最长回文子串长度
作者:熔遁丶螺旋手里剑 发布时间:2022-09-29 13:56:32
给定一个字符串,求它最长的回文子串长度,例如输入字符串'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
再给大家分享一个实例:
#!usr/bin/env python
#encoding:utf-8
'''
__Author__:沂水寒城
功能:寻找最长回文子序列
'''
def slice_window(one_str,w=1):
'''
滑窗函数
'''
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):
'''
主函数,寻找最长回文子序列
'''
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)
结果如下:
abcdcba
abcba
bb
abcba
[Finished in 0.3s]
来源:http://www.cnblogs.com/baiyb/p/8326216.html
猜你喜欢
- 需求:启动程序后,让用户输入工资,然后打印商品列表允许用户根据商品编号购买商品用户选择商品后,检测余额是否够,够就直接扣款,不够就提醒可随时
- 一、线性回归的理论1)线性回归的基本概念线性回归是一种有监督的学习算法,它介绍的自变量的和因变量的之间的线性的相关关系,分为一元线性回归和多
- 我们知道,关系型数据一般以规范化的形式保存,也就是说你应该尽可能少地重复数据;在正常情况下,表与表之间仅通过各种键值实现关联。进一步地讲,规
- 支持聚合函数的方法:提到聚合函数,首先我们要知道的就是这些聚合函数是不能在django中单独使用的,要想在django中使用这些聚合函数,就
- 我们先看一个简单的例子:<input type="text" onblur="alert(this.va
- 看过一篇关于下载网页中图片的文章,它只能下载以http头的图片,我做了些改进,可以下载网页中的所有连接资源,并按照网页中的目录结构建立本地目
- 最近做的一个B/S项目,在打印时采用了在IE中嵌入.net winform控件和XML结合的方式(参见http://www.yesky.co
- 切换按钮是QPushButton的特殊模式。它是一个具有两种状态的按钮:按压和未按压。我们通过这两种状态之间的切换来修改其它内容。#!/us
- <% Rem Rem ## 在线升级类声明 Class Cls_oUpdate
- 本文实例讲述了Python中迭代的用法,是一个非常实用的技巧。分享给大家供大家参考借鉴之用。具体分析如下:如果给定一个list或tuple,
- 2003年以来,网页的平均尺寸已经增长3倍。从2003到2008,网页的平均尺寸从93.7K增至312K,增幅233%。同时,在这5年之内,
- 我们在使用Django过程中,数据库往往是离不开的,比较长常用的是MySQL数据库,但在使用过程中,对Python不同的版本对用的库也不一样
- XML同HTML一样,都来自Standard Generalized Markup Language, 即标准通用标记语言,简称SGML。早
- Javascript有没有内存泄露?如果有,如何避免?鉴于最近有好几个人问到我类似的问题,看来大家对这部分内容还没有系统的研究过,因此,打算
- 导语一直以来,中国象棋都是中华民族的一种象征,当然也是人们最为喜感的一种娱乐方式。在若干年前,人们都习惯于约上自己的棋友,来一种激战。可是,
- 本书的作者Douglas Crockford是JavaScript开发社区最知名的权威,JavaScript的发明人Brendan Eich
- 本文实例讲述了Python MongoDB 插入数据时已存在则不执行,不存在则插入的解决方法。分享给大家供大家参考,具体如下:前言:想把QQ
- 导语好消息!下一个假期已经在路上了,正在向我们招手呢!大家只要再坚持5天就能迎来中秋小长假啦~“海上生明月,天涯共此时”又是一年中秋至!快跟
- 众所周知,Jupyter notebook是一个交互式的Python shell,也就是IPython的封装版,非常适合用来进行数据分析和机
- 前言日常工作中我们经常接触到一些文本类信息,需要从文本中解析出数据信息,然后再进行数据分析操作。而对文本类信息进行解析是一件比较头秃的事情,