动态规划之马拉车算法

Kubrnete 等级 454 0 0

问题描述:

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。如"abc"有三个回文子串‘a','b','c'.

示例 1:

输入:"abc" 输出:3 解释:三个回文子串: "a", "b", "c"

示例 2:

输入:"aaa" 输出:6 解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

对于这个问题,简单的思路是枚举字符串中的每个子串,然后判断子串中回文串的个数。O(N^3)

本篇文章主要介绍我个人对马拉车算法实现思路的一些想法,原题解请看leetcode-647.回文子串


中心拓展法

由于回文串有对称性这一特点,每个回文串必然存在一个对称中心。我们可以对字符串中每个字符或两个字符之间的位置(若回文串长度为偶数)当作对称中心进行枚举,例如s="abcba",当i=2时,判断a[1]==a[3],a[0]==a[4].....如果左右两边字符相同时则继续扩展,一旦不相同则更新最大扩展长度并退出当前循环,继续枚举下一个对称中心。

假设字符串的长度为 n,枚举每个对称中心(长度为 1 和 0的对称中心分别有 n 和 n-1 个),共遍历2n-1次,时间复杂度为 O(n);每个对称中心最多向外拓展n次,所以整体的时间复杂度是 O(n^2)。空间复杂度为O(1)。

代码如下(直接抄leetcode了):

//遍历2n-1次,就能够得到所有可能的对称中心
for (int i = 0; i < 2 * n - 1; i++) {
            int l = i / 2, r = i / 2 + i % 2;//这样能够把长度为奇数和偶数的两种情况统一起来。
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
                ++ans;
            }
        }

动态规划之马拉车算法

还有没有优化的空间呢?让我们看看在中心拓展法中出现的两个问题,然后了解一下马拉车算法如何对这两个问题进行处理。

1. 长回文串中的重复查找(关键):

为了更简单直接地说明问题,我举一个极端的特例:字符串s="aaaaaaa",并先对奇回文子串进行查找。尽管我们在以第2位字符为对称中心左右扩展时能够发现左回文子串s1="aaa",并且以第四位字符为对称中心左右扩展能够发现了长回文串s,那么之后的查找中是否仍需要匹配后三位字符串呢?设Im为长回文串的对称中心

动态规划之马拉车算法

动态规划之马拉车算法

其实,我们可以发现,若在一个长回文串中发现了左回文子串,根据回文串的对称性,那么在一定区域内的右子串中必然也存在一个回文串。因此,上述重复查找过程是可以省去的。

2.对长度奇数或偶数的回文子串分情况讨论

马拉车算法:

一、算法分析:

马拉车算法的核心思路就在于,对每个长回文串的对称中心向两边进行拓展,同时记下前面已经查找过的回文子串半径(原理是动态规划的思想),其本质在于,如果能够找到一个长回文串,同时在它的对称中心左区域中找到一个回文子串,由于回文串的对称性,其右区域中必然是同样的回文子串。因此这个算法能快速地找出最长的回文子串。当然也能用来求解回文子串的个数。

二、算法实现:

1.预处理(解决了奇偶回文串问题):

  • 为了利用回文串的对称性,同时解决回文子串长度有奇数和偶数两种情况的问题,马拉车算法在字符串首尾及每个字符间都插入一个 "#"。可以发现,无论回文子串原来是奇数还是偶数,最终都会变成奇回文子串,因此能够统一处理。即令原字符串为s,预处理后有 ts = s.replace('', '#')

  • 我们定义①

    当前向两边拓展距离最大的回文串为最大回文串,即一个长回文串;②

    从对称中心到左端点的距离为最大回文半径,并假设为d;

    当我们求出最大回文半径d时,

    最大回文串

    的长度正好是d。

    动态规划之马拉车算法

    动态规划之马拉车算法

  • 另外,在下面的步骤中,为了避免数组越界,我们还要在字符串开头加一个"$",结尾加一个"!",这样开头和结尾的两个字符一定不相等,循环就可以在这里终止。

预处理代码如下

s = '$' + input().replace('', '#') + '!'
#为了避免数组越界,让开头和结尾的两个字符一定不相等,循环就可以在这里终止。

动态规划之马拉车算法

2.初始化(解决了重复查找问题):

  • 数据结构与逻辑变量:马拉车算法的要求维护的变量有,一个数组d[]记录最大回文半径,d[i]表示以第i位元素为对称中心的最大回文半径,初始化长度为0(半径算上中心就是1);当前最大回文串的(即长回文串)对称中心Im及其右端点r,初始化皆为0。
  • 初始化
  • 以字符串"dadbdac"为例

动态规划之马拉车算法

动态规划之马拉车算法

这里有两种情况:

  • Case 1: i<=r,即当前枚举的对称中心i被包含在当前最大回文串内,此时拓展过程可以加速
  1. 当找到一个长回文串时,取其对称中心为Im,对于其中的每个对称中心i,我们可以求出关于Im的对称位置 j=2*Im-i
  2. 在这个长回文串范围内,可以通过对称性得到d[i]=d[j] 。
  3. 注意当d[j]>r-i时,通过d加速拓展的右子串超出了长回文串的范围。然而大于右端点的回文串我们还没有开始匹配,此时d[i] = r - i . 比方说,当Im=3时,有r=5;当i=5时,有j=1,并且前面已经算出d[j] = 1。此时d[j]>r-i,向右拓展超出了长回文串范围,则d[i]应为i到右端点r的距离,即r-i。因此,当对称中心i被包含在当前最大回文串内时,有

d[i]=min(d[2 * Im - i],r - i) (核心:如果d[j]+i<=r,则d[i]=d[j],否则d[i]=r-i)

  • Case 2 : i>r\,此时用常规的中心拓展法更新d[]、Im以及r。

3.中心拓展

经过了上面的初始化,我们每次枚举对称中心的时候就都能够保证 s[i-d[i]]=s[i+d[i]],而现在,只要再满足ts[i - d[i]-1]==ts[i + d[i]+1],则不断向左右两边拓展半径。

综上所述,我们能够写出马拉车算法的核心代码:

for i in range(2, len(s)-2):      
    if(i<=r):#当对称中心i被包含在当前最大回文串内时,拓展过程可以加速(核心)
        d[i]=min(d[2 * Im - i] , r - i )
    while (s[i - d[i] - 1] == s[i + d[i] + 1]):#满足条件,向左右拓展半径
        d[i] += 1

动态规划之马拉车算法

4.维护当前最大回文串的对称中心Im和r

我们仍以字符串"dadbdac"为例,求d时可以只看s[2:len-2):

s $ # d # a # d # b # d # a # c # !
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
d[i] 1 0 3 0 1 0 5 0 1 0 1 0 1

其实在上述的核心思路中,在枚举每个回文子串的对称中心时,也在不断匹配最大回文串并更新Im和r。利用已经算出来的状态来更新d[i],这就是一种动态规划的思想

对于一个回文串,我们用d[i]记录了其对称中心到右端点的距离。以上面的例子来说明,当i=8时(属于i>r的情况),计算出d[i]=5,则此时容易得到r=i+d[i]=13,同时更新Im=8。对于i<=r的情况,如果i+d[i]>r,说明当前对称中心i拓展出了回文串,于是此时需要更新对称中心Im为i,右端点r为i+d[i]。而对于i>r的情况,由于d[i]总是等于0,此时更新Im=i,r=i

if (i + d[i] > r):
    Im, r = i, i + d[i]

动态规划之马拉车算法

顺带提一句,最开始我以为马拉车这个算法名字应该是根据Manacher英译而来,但是这个中心扩展的思路,加上通过d[i]记录了最大回文串的半径避免了重复匹配,光看这两行代码:

while (s[i - d[i] - 1] == s[i + d[i] + 1]) d[i]++;
if (i + d[i] > r){Im=i, r = i + d[i];}

动态规划之马拉车算法

真是有两头马在拉着一个对称中心向两边跑的感觉,大概就像这样:动态规划之马拉车算法)动态规划之马拉车算法

然后不断更新最大回文串的对称中心Im和 r,通过***d[i] = min(d[2 \ Im - i], r - i)快速求解**

如何求解ans就不解释啦,直接上代码:

s = '$' + input().replace('', '#') + '!'
d,Im,r,ans= [0]*(len(s)-2),0,0,0
for i in range(1, len(s)-2):    
    if (i <= r):#当对称中心i被包含在当前最大回文串内时,拓展过程可以加速
        d[i] = min(d[2 * Im - i], r - i) #核心:如果d[j]+i<=r,则d[i]=d[j],否则d[i]=r-i
    while (s[i - d[i] - 1] == s[i + d[i] + 1]):#满足条件,向左右拓展半径
        d[i] += 1
    if (i + d[i] > r):
        Im, r = i, i + d[i]
    ans += (d[i] + 1) // 2
print(ans)

动态规划之马拉车算法

这个算法总时间复杂度是O(n),空间复杂度O(n)。

另外,如果再用一个变量ma记录d[i]的最大值,稍微改一下最后两行,就可以找出字符串中的最长回文子串:

ma,ans = (d[i],ts[i-d[i]:i+d[i]]) if (d[i]>ma) else (ma,ans)
print(ans.replace('#',''))

本文转自 https://blog.csdn.net/guanguandaren/article/details/108105363,如有侵权,请联系删除。

收藏
评论区

相关推荐

一文搞懂什么是HTTP与HTTPS
(https://blog.csdn.net/petterp/article/details/102779257)Http与Https的区别。 在最近的开发中,深感网络相关基础知识薄弱,于是趁周末好好总结一
15. Python 程序运行速度如何提高十倍?第一遍滚雪球学 Python 收工
本篇文章将给大家介绍 Python 多线程与多进程相关知识,学习完该知识点之后,你的 Python 程序将进入另一个高峰。 <center<font colorred缓解一下视疲劳</font</center 15. Python 程序运行速度如何提高十倍?第一遍滚雪球学 Python 收工(https://imghelloworld.oss
动态规划之马拉车算法
问题描述: 给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。如"abc"有三个回文子串‘a','b','c'. 示例 1: 输入:"abc" 输出:3 解释:三个回文子串: "a", "b", "c" 示例 2: 输入:"aaa" 输出
20 张图彻底弄懂 HTTPS 的原理
前言 近年来各大公司对信息安全传输越来越重视,也逐步把网站升级到 HTTPS 了,那么大家知道 HTTPS 的原理是怎样的吗,到底是它是如何确保信息安全传输的?网上挺多介绍 HTTPS,但我发现总是或多或少有些点有些遗漏,没有讲全,今天试图由浅入深地把 HTTPS 讲明白,相信大家看完一定能掌握 HTTPS 的原理,本文大纲如下: HTTP 为什么不安全
推荐程序员必备的 10 大 GitHub 仓库,前端占了 7 个!
大家好,我是你们的 猫哥,一个不喜欢吃鱼、又不喜欢喵 的超级猫 关于猫哥,大家可以看看我的年终总结 前端工程师的 2020 年终总结 乾坤未定,你我皆黑马(https://github.com/biaochenxuying/blog/issues/79)。 前言 初级前端与高级前端之间,很大原因就是投入学习前端的时间、经验的差别,其实就
简单盘点12个Python数据可视化库,通吃任何领域
(https://imghelloworld.osscnbeijing.aliyuncs.com/a7ecca0969cf04ff24e7c734e3cb73df.png) 大家好,我是小五🐶 在数据可视化的研究热潮中,如何让数据生动呈现,成了一个具有挑战性的任务,随之也出现了大量的可视化软件。相对于其他商业可视化软件,Python
木马病毒你需要知道的15个技术点。
木马病毒方式1:模块通过三方签名过杀毒检测,注册表进行开机启动,通过url进行数据传递,释放不同exe或者文件进行木马功能,感染的dll数据会通过加密,会通过注入explorer.exe,services.exe,spoolsv.exe进行功能实现。木马病毒方式2: 通过向系统进程services.exe, explorer.exe,svchost.exe注
Django+Vue开发生鲜电商平台之3.数据模型设计和资源导入
永远不要跟别人比幸运,我从来没想过我比别人幸运,我也许比他们更有毅力,在最困难的时候,他们熬不住了,我可以多熬一秒钟、两秒钟。 ——马云Github和Gitee代码同步更新:;。在正式开发项目之前,要确定数据库和表结构。 一、项目初始化在虚拟环境安装好之后,需要安装Django和Django REST framework,直接
小伙子不讲武德,竟用Python爬取了B站上1.4w条马老师视频数据来分析
看到标题, 啪的一下你就进来了吧!如果有经常刷B站的小伙伴,肯定都知道B站鬼畜现在的顶流是谁?印度:没错正是在下那必须是当代大师浑元形意太极拳掌门人「马保国」先生啊!实话讲,马保国走进大家视野还是他5月份PK被人连续KO三次。不过现在他在鬼畜区的主要素材却是马保国更早时候的一些视频。比如2020年一月份,右眼被蹭了一下的马老师面带微笑,为我们生动形象地讲述
用Python生成自己专属的手机春节壁纸
↑ 关注 + 置顶  有趣的不像个技术号 大家好,我是朱小五 马上就要过年了,要不要换一个喜气洋洋、洋洋洒洒、洒扫应对、对牛弹琴的手机壁纸呢? 今天小五给大家表演的节目是:用Python生成自己独一无二的手机壁纸。 首先我们需要选择一个现成的手机壁纸作为模板,我选择了这种以自己姓氏为主题的专属手机壁纸。<<  左右滑动查看更多  这其实是个之
https://cloud.tencent.com/developer/article/write/1830331
一、目标今天的目标是这个sign和appcode 二、步骤 Jadx没法上了app加了某梆的企业版,Jadx表示无能为力了。 FRIDADEXDumpDexDump出来,木有找到有效的信息。 Wallbreaker葫芦娃的Wallbreaker可以做些带壳分析,不过这个样本,用Frida的Spawn模式可以载入,Attach模式会失败。而直接用Objecti
618抢购抢不到?,会了python的这个骚操作,妈妈再也不担心我抢不过别人了!!!
618马上要到了,像淘宝,天猫,京东早就已经准备好了,每到618与双十一这种消费盛典,便会抢购的现象,很多人因为手速不够快,抢不到价格实惠的商品,在这小编给大家带来了一个自动抢购的示例代码,此代码是python通过selenium实现毫秒级的自动抢购。(该文章仅作学习selenium框架的学习示例)直接上源码:!/usr/bin/env python cod
小红书很难爬?最新爬取方法教给你啦~
Python进击者第184篇原创文章前言大家好,我是Kuls。之前写的那篇App抓包软件charles的配置说过,超过30在看,马上更下一篇。所以加班加点给大家写了今天这篇文章。本文将会带着大家完完整整的爬取小红书的全过程 小红书需要做的前提工作就是装配好mitmproxy具体的配置过程,我建议大家参照崔大写的来进行安装https://zhuanlan.z
小伙子不讲武德,竟用Python爬取了B站上1.4w条马老师视频数据来分析
看到标题,啪的一下你就进来了吧!如果有经常刷B站的小伙伴,肯定都知道B站鬼畜现在的顶流是谁?印度:没错正是在下那必须是当代大师浑元形意太极拳掌门人「马保国」先生啊!实话讲,马保国走进大家视野还是他5月份PK被人连续KO三次。不过现在他在鬼畜区的主要素材却是马保国更早时候的一些视频。比如2020年一月份,右眼被蹭了一下的马老师面带微笑,为我们生动形象地讲述了健
PI黑客马拉松近期工作汇报
嘿,PI开拓者!下面,Pi 核心团队将发布我们buildpi2gether黑客马拉松研讨会视频的总结,介绍如何利用不同的 Pi 资源来构建您的项目。让我们知道,如果有什么我们可以做的,使我们的内容更容易访问!黑客马拉松工作坊视频 1 标题: Pi 开发人员门户介绍https://www.bilibili.com/video/BV1tw41197Vp/?ai