Manacher算法

我们知道优化非启发性算法的方法常常包括使用定理、利用计算机的架构特点、使用恰当的数据结构以及动态规划等。而动态规划的核心理念就是减少重复计算。
对于回文串问题的Manacher算法来说,我们要重用0..(i-1)的结果,那怎么重用呢?假设ij关于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 >= 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 <= p + R[p]$是才会执行这一步。
$j+R[j]$与$p$的位置关系决定了$i+R[j]$和$p+R[p]$的位置关系。

  1. 在内部
    当$j+R[j] <= p$,则$i+R[j] <= 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$,然后从这个半径向外开始暴力

偶数长度的回文串

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