python最长回文串算法
作者:熊熊不爱说话 发布时间:2023-03-05 02:27:37
给定一个字符串,要求在这个字符串中找到符合回文性质的最长子串。所谓回文性是指诸如 “aba”,"ababa","abba"这类的字符串,当然单个字符以及两个相邻相同字符也满足回文性质。
看到这个问题,最先想到的解决方法自然是暴力枚举,通过枚举字符串所有字串的起点,逐一判断满足回文性的子串,记录长度并更新最长长度。显然这种算法的时间复杂度是很高的,最坏情况可以达到O(N*N)。所以呢,这里提出一个优化的方案,通过枚举字符串子串的中心而不是起点,向两边同时扩散,依然是逐一判断子串的回文性。这种优化算法比之前的算法在最坏的情况下(即只有一种字符的字符串)效率会有很大程度的上升。
由上述的优化方案,我们知道了枚举中心要比枚举起点效率要好,然而这并不是最优的算法。由于枚举中心的算法同时影响的是中心两边的字符,所以我们可以通过枚举中心的左边字符作为中心的子串的回文性判断枚举中心右边的字符作为中心得子串的回文性,这就是manacher算法。
manacher算法思想非常巧妙,首先遍历字符串,假设 i 为枚举中心,则 j (j<i) 为中心的最长回文子串长度发f[j] 便已经求出,此时 j 的影响范围便是[j-f[j]/2,j+f [j]] 。为了使左边的字符 j 对枚举中心右边的影响最大,需要使 j+f[j]/2 最大。找到满足j+f[j]/2最大的 j 之后,若 i 在[j,j+f[j]/2]中,则分两种情况:
1 . i 关于 j 对称的字符i'的影响范围完全包含在j的影响范围内,则由于回文性,i 的影响范围大于等于i'的影响范围,即f[i]>=f[i']
2. i 关于 j 对称的字符i'的影响范围不完全包含在j的影响范围内,此时i的右侧影响范围大于等于[j-f[j]/2,i'],即i+f[i]/2>=i'-j+f[j]/2
由于对称性,可得i+i" = 2*j。因此第一种情况下,f[i]>=f[2*j-i];第二种情况下,f[i]>=f[j]+2*j-2*i。
综上1,2,可得f[i]>=min(f[2*j-i],f[j]+2*j-2*i)。由于i右边存在未遍历的字符,因此在此基础上,继续向两边扩展,直到找到最长的回文子串。
若i依然在j+f[j]/2后面,则表示i没有被前面的字符的影响,只能逐一的向两边扩展。
这个算法由于只需遍历一遍字符串,扩展的次数也是有限的,所以时间复杂度可以达到O(N)。
下面是Pthon3的程序,为了检测算法的效率,依然提供最初的暴力枚举算法作为最坏算法的参照。
python代码:
#求最长回文串类
class LPS:
#初始化,需要提供一个字符串
def __init__(self,string):
self.string = string
self.lens = len(self.string)
#暴力枚举:作为算法效率参照
def brute_force(self):
maxcount = 0
for j in range(self.lens):
for k in range(j,self.lens):
count = 0
l,m = j,k
while m>=l:
if self.string[l]==self.string[m]:
l,m = l+1,m-1
else:
break
if m<l:
count = k-j+1
if count>maxcount :
maxcount = count
return maxcount
#优化版:枚举子串中心
def brute_force_opti(self):
maxcount = 0
if self.lens == 1: #只有一个字符直接返回1
return 1
for j in range(self.lens-1): #枚举中心
count,u = 1,j
#对于奇数子串,直接扩展
for k in range(1,j+1): #两边扩展
l,m = u+k,j-k
if (m>=0)&(l<self.lens):
if(self.string[l]==self.string[m]):
count += 2
else:
break
if count>maxcount : #更新回文子串最长长度
maxcount = count
if self.string[j]==self.string[j+1]: #处理偶数子串,将两个相邻相同元素作为整体
u,count= j+1,2
for k in range(1,j+1): #两边扩展
l,m = u+k,j-k
if (m>=0)&(l<self.lens):
if(self.string[l]==self.string[m]):
count += 2
else:
break
if count>maxcount : #更新回文子串最长长度
maxcount = count
return maxcount
#manacher算法
def manacher(self):
s = '#'+'#'.join(self.string)+'#' #字符串处理,用特殊字符隔离字符串,方便处理偶数子串
lens = len(s)
f = [] #辅助列表:f[i]表示i作中心的最长回文子串的长度
maxj = 0 #记录对i右边影响最大的字符位置j
maxl = 0 #记录j影响范围的右边界
maxd = 0 #记录最长的回文子串长度
for i in range(lens): #遍历字符串
if maxl>i:
count = min(maxl-i,int(f[2*maxj-i]/2)+1)#这里为了方便后续计算使用count,其表示当前字符到其影响范围的右边界的距离
else :
count = 1
while i-count>=0 and i+count<lens and s[i-count]==s[i+count]:#两边扩展
count +=1
if(i-1+count)>maxl: #更新影响范围最大的字符j及其右边界
maxl,maxj = i-1+count,i
f.append(count*2-1)
maxd = max(maxd,f[i]) #更新回文子串最长长度
return int((maxd+1)/2)-1 #去除特殊字符
通过上面的程序,使用字符串为长度1000的纯‘a'字符串作为样例,经过测试:
暴力枚举:49.719844s
中心枚举:0.334019s
manacher:0.008000s
由此可见,长度为1000时,暴力枚举的耗时已经无法忍受了,而相比而言,中心枚举在效率上已经有很大幅度的提升,最优的manacher耗时则为更短。
来源:https://blog.csdn.net/backkom_lory/article/details/53896664
猜你喜欢
- 在研究ezSQL的时候就看到了mssql_connect()等一些php提供的连接MSSQL的函数,本以为php这个开源的风靡世界的编程语言
- Microsoft? SQL Server? 2000 的可用版本如下:SQL Server 2000企业版作为生产数据库服务器使用。支持
- 安装conda activate ps pip install visdom激活ps的环境,在指定的ps环境中安装visdom开启pytho
- 英语原文地址:点此浏览新年开始了,来点猛料,放上15个漂亮的网页排版的demo,来欣赏一下。去年我也专门找了15个同类网站,比较受用户欢迎,
- 很神奇的一个晚上,居然在以前老同事的群里跟同事讨论起CSS的东西来了,不过很意外的还是有收获。在IE中常常会碰到如果将容器定位后,出现容器内
- 1.准备工作:工欲善其事必先利其器,因此我们有必要在进行Coding前先配置一个适合我们自己的开发环境,我搭建的开发环境是:操作系统:Ubu
- 思路有些混乱,希望大家能理解我的意思。看了faster rcnn的tensorflow代码,关于fix_variables的作用我不是很明白
- python的字符串编码识别模块(第三方库):官方地址: http://pypi.python.org/pypi/chardetimport
- 很多时候,查看一个文件夹下的每个文件大小可以轻易的做到,因为文件后面就是文件尺寸,但是如果需要查看一个文件夹下面所有的文件夹对应的尺寸,就发
- 代码如下:create table T_NEWS ( ID NUMBER, N_TYPE VARCHAR2(20), N_TIT
- 1.实例方法Python 的实例方法用得最多,也最常见。我们先来看 Python 的实例方法。class Kls(object): &nbs
- 具体用法如下: 代码如下:-- ============================================= -- Autho
- 本文实例为大家分享了python封装对象实现时间效果的具体代码,供大家参考,具体内容如下# 钟表import timeclass Clock
- 享元模式(Flyweight Pattern)是什么享元模式是一种结构型模式,它通过共享对象来减少系统中的对象数量,从而降低了内存的使用和系
- 本文实例讲述了Python通用循环的构造方法。分享给大家供大家参考,具体如下:1.交互循环是无限循环的一种,允许用户通过交互的方式程序的特定
- 本文实例讲述了python实现Oracle查询分组的方法。分享给大家供大家参考,具体如下:1.分组的概念:关键字:group by子句结论:
- 一、实现创建文件夹和日志#!/usr/bin/env python# -*- coding:utf-8 -*-# Author: nulig
- 用法: 按住鼠标左键拖拽一个框后释放洗洗睡了<!DOCTYPE html public "-//W3C//DTD XHTML
- Python2.7已于2020年1月1日开始停用,之前RF做自动化都是基于Python2的版本。没办法,跟随时代的脚步,我们也不得不升级以应
- Merge函数的用法简单来说Merge函数相当于Excel中的vlookup函数。当我们对2个表进行数据合并的时候需要通过指定两个表中相同的