Manacher

一、背景

1975年，Manacher发明了Manacher算法（中文名：马拉车算法），是一个可以在O(n)的复杂度中返回字符串s中最长回文子串长度的算法，十分巧妙。

让我们举个栗子，栗子：

1.字符串：abbababa        最长回文子串：5（abbababa）

2.字符串：abcbbabbc      最长回文子串：7（abcbbabbc）

3.字符串：abccbaba        最长回文子串：6（abccbaba）

传统方法是，遍历每个字符，以该字符为中心向两边查找。时间复杂度为O(n^2)，效率很差；

而这个神奇的Manacher算法将复杂度提升到了O(n)。

来一起瞅一瞅它是如何工作的吧。

二、算法过程分析

回文分为奇回文（ababa）和偶回文（abba），这里比较难以处理，我们使用一个小(sao)技(cao)巧(zuo)（很重要）。我们将字符串首尾和每个字符间插入一个字符（注意：这个自符在串中并未出现）例如：'#'.

栗子！栗子！s='abbadcacda'先转化成s_new='$#a#b#b#a#d#c#a#c#d#a#\0'（'$'与'\0'，是边界，下面的代码中可以看到）

这样原串中的偶回文（abba）与奇回文（adcacda），变成了（#a#d#d#a#）与（#a#d#c#a#c#d#a#）两个奇回文。

定义数组p[]，用p[i]表示以i为中心的最长回文半径。栗子在这里：

那，p[i]该如何求呢？很显然，p[i]-1正好就是原字符中的最长回文串长度了。

让我们一起找到正解。

请看下图：

定义两个变量mx和id。mx就是以id为中心的最长回文右边界，也就是mx=id+p[id]，随后我们需要mx做出它的最大贡献。

假设我们在求p[i]（以i为中心的最长回文半径），如果i