我们知道优化非启发性算法的方法常常包括使用定理、利用计算机的架构特点、使用恰当的数据结构以及动态规划等。而动态规划的核心理念就是减少重复计算。
对于回文串问题的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]$的位置关系。
- 在内部
当$j+R[j] \le p$，则$i+R[j] \le p+R[p]$，这就相当于以$i$至少有一个以$R[j]$为半径的回文串，并且在以$p$为中心的回文串的内部。预示我们只需要从$R[j]+1$开始检测$i$位置是否具有更大半径即可。 - 在外部
当$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)$
偶数长度的回文串
这个时候就没办法定义“半径”这个概念了，有一个巧妙的方法是将其变为奇数长度的回文串，也就是在头尾以及每个字符中间加入一个特殊字符。
