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算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程