我们知道优化非启发性算法的方法常常包括使用定理、利用计算机的架构特点、使用恰当的数据结构以及动态规划等。而动态规划的核心理念就是减少重复计算。
对于回文串问题的Manacher算法来说，我们要重用0..(i-1)的结果，那怎么重用呢？假设i和j关于p(i > p > j)对称，那么R[i]便可通过R[j]求得。
计算最长回文串的暴力算法是O(n^2)，而马拉车算法能够在O(n)时间内解决问题。

Manacher算法

我们使用$R[i]$表示$i$位置处的回文半径，即字符串$aba$中$b$字符的回文半径为2。我们现在使用$i$从左开始遍历字符串求$R[i]$，为了能够DP，我们假设有一个合适的$p \lt i$，我们把$i$关于$p$做对称得到$j$。注意到$R[j]$、$R[p]$是已求得的，待求$R[i]$。
此时字符串坐标轴上出现了五个刻度：$p$、$j$、$i$、$j+R[j]$、$p+R[p]$，我们需要讨论他们的位置关系。由假设有$j < p < i$，可是$j+R[j]$、$p+R[p]$关系不好确定，为了方便讨论，我们可以假设这个“合适的”$p$满足$p+R[p] > j+R[j]$。这是因为在后面的讨论中我们发现要使得$p+R[p]$尽可能大，假如$p+R[p] < j+R[j]$，也就是以$j$为中心的回文串的右边界比以$p$为中心的右边界还要靠右，那么我们与其取$p$，不如直接取$j$，而且$j$也是在$p$前面被遍历。
现在我们可以得到三组位置关系

$$\begin{equation}\begin{split} j &< j + R[j] < p + R[p] \\ j &< p < p + R[p] \\ p &< i \\ \end{split}\end{equation}$$

可以看出只有$j + R[j]$与$p$、$i$和$p + R[p]$这两个位置关系尚未确定。在下面的讨论中，我们发现只有这两个都满足一定关系时，才能够重用结果。

$p + R[p]$和$i$的位置关系

当$i \ge p + R[p]$时，$i$已经在$p$为中心的回文串外面了，以$i$中心的回文串看来是借不了这个$p$的东风了，我们需要重新找一个“回文边界”更靠右的$p$。所以我们直接维护一个$p’$，使得$p’+R[p’]$始终是最大的，如果这最大还不够大，即这边界最靠右的$p$都包不住$i$，那$i$便只能自力更生暴力一波了。

$j + R[j]$与$p$的位置关系

根据上节讨论，$i > p + R[p]$时只能暴力，并且$j$有可能越界到小于0，所以只有$i \le p + R[p]$是才会执行这一步，我们认为现在$j \lt p \lt i \le p + R[p]$。
$j+R[j]$与$p$的位置关系决定了$i+R[j]$和$p+R[p]$的位置关系。

1. 在内部
   当$j+R[j] \le p$，则$i+R[j] \le p+R[p]$，这就相当于以$i$至少有一个以$R[j]$为半径的回文串，并且在以$p$为中心的回文串的内部。预示我们只需要从$R[j]+1$开始检测$i$位置是否具有更大半径即可。
2. 在外部
   当$j+R[j] > p$，则$i+R[j] > p+R[p]$，这就相当于$j$中心回文串的边界在$p$中心的回文串的边界之外，所以我们只能重用$j$中心回文串在$p$内的对称部分，其半径为$2 \times R[j] - R[p] + j - p$，然后从这个半径向外开始暴力

我们发现这两个情况可以直接合并取一个半径的最小值$min(R[j], 2 \times R[j] - R[p] + j - p)$

偶数长度的回文串

这个时候就没办法定义“半径”这个概念了，有一个巧妙的方法是将其变为奇数长度的回文串，也就是在头尾以及每个字符中间加入一个特殊字符。

模板代码