leetcode5 longest palindrome substring 之manacher算法

本文主要是介绍leetcode5 longest palindrome substring 之manacher算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这个题的常规解法大家可以看答案，还是很简单直接的。这里我想用自己比较易懂的语言，讲一下可以达到o(n)的manacher算法，希望可以帮助有兴趣的盆友思考。

首先要引入臂长的概念，比如abcba，以c为中心，那么臂长是2。

接下来我们考虑，关于某中心回文上对称的两个点，比如上面abcba上的两个b点，应该有对称的效果。（它俩所在的回文就叫原始回文吧。）

左点的臂长如果是不超过原来回文的臂展的，也就是是个小回文，那右点应该至少也拥有这个小回文的臂长。（图片上面的回文，绿点应该至少有红点同样的小臂长）

那么，如果左点的臂长比较大，超过了原始回文臂展范围呢？右点是否还回和左点臂长一样？答案就是不一定了。（图片下面的回文，当红点的范围超过了原始回文，绿点可以拥有这样的大臂长嘛？答案是否定的。）

因为，红绿两点的对称性，只在原始回文范围内有效，一旦超过了原始回文的范围，超出的点是否等于红点对称的点，我们没比过没数据不知道，要亲自比一比才行。所以答案是不知道。万幸的是，红绿两点的黄色部分是一样的回文，那么红点臂长至少有黄回文那么长。

这两种case综合一下，用计算机的语言写出来，就是红点臂长我们可以肯定至少有，min(绿点臂长, 黄回文臂长）这么长。

这个策略就让我们面对一个新的回文中心时，可以不用从1来++实验臂长，而是把它看作右边的绿点，找到对应的红点，站在过去data的肩膀上，从上面提到的min（绿回文臂长，黄回文臂长）这样作为起点，继续两边看

这篇关于leetcode5 longest palindrome substring 之manacher算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！