leetcode5 longest palindrome substring 之manacher算法
2021/10/6 17:12:48
本文主要是介绍leetcode5 longest palindrome substring 之manacher算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这个题的常规解法大家可以看答案,还是很简单直接的。这里我想用自己比较易懂的语言,讲一下可以达到o(n)的manacher算法,希望可以帮助有兴趣的盆友思考。
首先要引入臂长的概念,比如abcba,以c为中心,那么臂长是2。
接下来我们考虑,关于某中心回文上对称的两个点,比如上面abcba上的两个b点,应该有对称的效果。(它俩所在的回文就叫原始回文吧。)
左点的臂长如果是不超过原来回文的臂展的,也就是是个小回文,那右点应该至少也拥有这个小回文的臂长。(图片上面的回文,绿点应该至少有红点同样的小臂长)
那么,如果左点的臂长比较大,超过了原始回文臂展范围呢?右点是否还回和左点臂长一样?答案就是不一定了。(图片下面的回文,当红点的范围超过了原始回文,绿点可以拥有这样的大臂长嘛?答案是否定的。)
因为,红绿两点的对称性,只在原始回文范围内有效,一旦超过了原始回文的范围,超出的点是否等于红点对称的点,我们没比过没数据不知道,要亲自比一比才行。所以答案是不知道。万幸的是,红绿两点的黄色部分是一样的回文,那么红点臂长至少有黄回文那么长。
这两种case综合一下,用计算机的语言写出来,就是红点臂长我们可以肯定至少有,min(绿点臂长, 黄回文臂长)这么长。
这个策略就让我们面对一个新的回文中心时,可以不用从1来++实验臂长,而是把它看作右边的绿点,找到对应的红点,站在过去data的肩膀上,从上面提到的min(绿回文臂长,黄回文臂长)这样作为起点,继续两边看
这篇关于leetcode5 longest palindrome substring 之manacher算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享