Manacher 算法

正文索引 [隐藏]

问题设定

回文字符串,就是一个字符串,你从前向后读它与从后向前读它是一样的。比如:baccab 就是一个回文串,而且是一个长度为偶数的回文串(偶回文串);bacdcab 是一个长度为奇数的回文串(奇回文串),babcb 就不是一个回文串。
这里可以发现,奇回文串的中心是一个字母,偶回文串的中心在最中心的两个字母间。

Manacher 要解决的问题:给你一个字符串 S,求出这个字符串内所有中心对应的最长回文子串。

我们首先要理解为什么要求这个东西,为啥不直接求出字符串内的所有回文子串?
因为一个字符串内的回文子串数量可能达到 $O(n^2)$ 级别,形如 aaaaaa 这样的字符串。
而中心不同的最长回文子串则为 $O(n)$ 级别(因为不同的中心仅有 $2n-1$ 个),同时求出它基本等价于我们求出字符串内的所有回文子串。中心不同的最长回文子串信息可以看作是字符串内所有回文子串信息的压缩形式。

ac
\underbrace{bc\hat{d}cb}
bb

假设我们求出了 $\hat{d}$ 为中心的最长回文子串是 bcdcb,那么同样以 d 为中心且比它短的子串 cdcd 也一定回文。相反的,如果要查询 cdc 是否回文,我们只需要看 cdc 的长度 3 是否小于等于同样中心为 d 的最长回文子串 bcdcb 的长度 5 即可。

暴力算法

枚举子串 + Check

最最暴力的方法是枚举字符串的任意一个子串,然后检查它是否回文,这样的复杂度为 $O(n^3)$。

换一种枚举的方式:枚举不同的子串中心,向外扩张寻找回文串。我们就可以将复杂度降低到 $O(n^2)$,因为这种方式利用了回文的对称性。


BruteForce

因为中心不同,所以奇回文串与偶回文串的代码处理略有不同。这里即后文都将仅关注奇回文子串,并在结尾给出统一奇、偶回文子串的方法。

二分 + 字符串哈希

这个块内容对于学习 Manacher 算法并不重要,仅仅作为科普以下暴力算法如何通过普通的字符串技巧进一步优化。

这里我们用到了一个很常见的组合字符串哈希 + 二分。字符串哈希是一种 $O(n)$ 预处理后,可以 $O(1)$ 比较已知字符串的两个子串是否相等的技术。二分是一种利用问题的单调性将原本线性搜索的复杂度降低为 $log_2$ 级别的技巧。

思路非常简单,当我们枚举了一个字符串的中心后,此中心对应的最长回文子串长度为 $p^*$。但是我们并不知道 $p^*$ 是多少,所以我们需要反复尝试不同长度 $\hat{p}$,然后用字符串哈希检查它是否回文。
显然,当 $\hat{p}\leq p^*$ 时子串是回文的,反之不是。这就满足了二分所需的单调性,我们利用二分的方法,找到一个最大的 $\hat{p}_{max}$ 满足对应的子串是回文的,就一定有 $p^*=\hat{p}_{max}$。


好了,此处没有动图

Manacher 算法

利用回文的对称性

先抛出核心思想,Manacher 算法充分利用了回文字符串的对称性,以此将 $O(n^2)$ 的暴力算法优化到 $O(n)$。

为了方便讲解算法的内涵,我们暂且只关注字符串 S 内所有的奇回文子串(偶回文子串的处理是完全类似的),同时用 $d_k$ 表示以位置 $k$ 为中心的最长回文子串向两边延伸多少。

我们从左到右计算 $d_i$,且假设当前要计算 $d_i$ 的值,也就是以 $S[i]$ 为中心的最长回文子串的长度。我们还要维护之前计算过的所有最长回文子串中结束位置最靠右的那个回文子串,记作 $S[l\ldots r]$。

假设 $i \in [l, r]$,也就是 $S[i]$ 在当前已知的最靠右最长回文子串中,如下图。(如果 $i \notin [l, r]$ 那就是没啥信息可以利用了,暴力计算 $d_i$ 吧)

\ldots
\overbrace{
S_l \ldots S_i \ldots S_r
}^\text{已知最右最长回文子串}
\ldots

因为 $S[l\ldots r]$ 是一个回文串,所以我们总可以根据回文的对称性寻找到位置 $j=l+r-i\in [l, r]$,且位置 $j$ 为中心的答案 $d_j$ 已经求出来了。
根据 $d_j$ 的大小不同,$S[j-d_j+1\ldots j + d_j-1]$ 与 $S[l\ldots r]$ 的位置关系可以分为三种情况:

\begin{aligned}
情况A:&
\ldots
\overbrace{
S_l \ldots
\underbrace{
S_{j-d_j+1} \ldots S_j \ldots S_{j+d_j-1}
}_\text{回文串}
\ldots S_i
\ldots S_r
}^\text{已知最右最长回文子串}
\ldots\\
情况B:&
\ldots
\overbrace{
\underbrace{
S_l \ldots S_j \ldots S_{j+d_j-1}
}_\text{回文串}
\ldots S_i
\ldots S_r
}^\text{已知最右最长回文子串}
\ldots\\
情况C:&\ldots\rlap{
$\underbrace{\phantom{S_{j-d_j+1}\ \ldots \ S_l\ \ldots\ S_j\ \ldots\ S_{j+d_j-1}}}_\text{回文串}$
}S_{j-d_j+1}\ \ldots \ \overbrace{S_l\ \ldots\ S_j\ \ldots\ S_{j+d_j-1}\ldots\ S_i\ \ldots S_r}^\text{已知最右最长回文子串}\ldots
\end{aligned}

对于情况 A:
我们再根据 $S[l\ldots r]$ 的对称性,我们可以立刻知道 $S[j-d_j+1\ldots j+d_j-1]$ 的对称位置 $S[i-d_j+1\ldots i+d_j-1]$ 也是回文的,而且 $S[i-d_j+1\ldots i+d_j-1]$ 一定是以 $S[i]$ 为中心的最长回文串,否则按照对称性 $d_j$ 就还可以增大,所以 $d_i = d_j$,我们利用回文串的对称性一下子求出了 $d_i$。

\ldots
\overbrace{
S_l \ldots
\underbrace{
S_{j-d_j+1} \ldots S_j \ldots S_{j+d_j-1}
}_\text{回文串}
\ldots
\underbrace{
S_{i-d_j+1} \ldots S_i \ldots S_{i+d_j-1}
}_\text{回文串}
\ldots S_r
}^\text{已知最右最长回文子串}
\ldots

对于情况 B:
同样根据对称性,我们可以知道 $S[i-d_j+1 \ldots r]$ 也是回文的,但是这里我们不能直接令让 $d_i$ 等于 $d_j$,事实上 $d_j$ 是 $d_i$ 的下界。因为当前已知最右最长回文子串的右侧是我们没有考察过的,如果 $S_{r+1} = S_{i-d_j}$,那么 $d_i$ 可以变得更大,至于到底可以多大,我们暴力尝试就可以了。

\ldots
\overbrace{
\underbrace{
S_l \ldots S_j \ldots S_{j+d_j-1}
}_\text{回文串}
\ldots
\underbrace{
S_{i-d_j+1} \ldots S_i \ldots S_r
}_\text{回文串}
}^\text{已知最右最长回文子串}
\ \underbrace{\ldots\ldots\ldots}_\text{未知区域}

对于情况 C:
$S[j-d_j+1\ldots j+d_j-1]$ 在 $S[l\ldots r]$ 之外的部分,我们没有办法利用回文串的性质对称过来了,而其余部分 $S[l\ldots j+d_j-1]$ 对称过来是 $S[i-(j-l)\ldots r]$,所以我们就可以知道 $d_i$ 起码可以等于 $j-l$。但是 $d_i$ 还能像情况 B 一样变得更大吗,答案是不能,如果 $d_i$ 还可以变得更大,那么就有 $S[r+1] = S[i-(j-l)-1] = S[j+(j-l)+1] = S[l-1]$,那么 $S[l\ldots r]$ 就不再是当前已知的最右最长回文子串了,和已知条件矛盾,所以 $d_i = j-l (= r – i)$。

\ldots
\overbrace{\underbrace{S_l\ \ldots\ S_j\ \ldots\ S_{j+(j-l)}}_\text{回文串}\ldots\ \underbrace{S_{i-(j-l)}\ \ldots\ S_i\ \ldots\ S_{r}}_\text{回文串}}^\text{已知最右最长回文子串}\ldots

别看情况有三种,其实可以使用同一套逻辑解决:

  • 通过最右最长回文子串 $S[l\ldots r]$ 得到对称位置 $j = l + r – i$
  • 暂且令 $d_i = min(d_j, j-l+1)$(这一步集合了三种情况)
  • 暴力尝试增大 $d_i$,即向外扩张回文子串
  • 得到 $d_i$ 后,尝试是否能够更新当前的 $S[l\ldots r]$

统一奇偶回文串

偶回文子串,也可以通过类似的代码处理得到,不过这里介绍一种方式可以将奇偶回文串巧妙地统一起来。

奇偶回文串唯一的区别在于,奇回文串的中心是一个字符,而偶回文串的中心在两个字符之间,这就让我们代码处理起来不够统一。

我们可以在所有字符间插入特殊字符,是的偶回文串的中心也是字符,例如:abcabc,我们在其中插入特殊符号 #,那么他就变成了 #a#b#c#a#b#c#,这样奇回文串的中心是原本的字符,偶回文串的中心就是我们插入的 # 字符了,至此奇偶回文串的处理代码便巧妙地统一了。

一不做,二不休,我们在回文串的首位再增加两个肯定不会匹配的字符 @$,使其变成 $#a#b#c#a#b#c#@,这样我们再判断相等的时候连越界都可以省了,因为到了边界一定不能匹配。

复杂度证明

与 KMP 相似,我们需要高级的复杂度证明技巧,不过这里可以非常简单的解释这件事情。

顺次枚举不同中心的复杂度显然是线性的,因为不同的中心仅有 $2*n-1$ 个。比较难以说明的是对于所有中心位置 $i$,使用暴力法尝试增加 $d_i$ 的总次数是否是线性的。

我们回到上一节的情况 A、情况 B、情况 C:

  • 情况 A:$d_i = d_j$,不用尝试 / 尝试即失败
  • 情况 B:$d_i = d_j$,每一次增大 $d_i$ 一定伴随着 $r$ 增大,因为 $r$ 不会变小,所以增加 $d_k,k\in[0,n)$ 的总次数最多为 $n$ 次,此情况复杂度之和为 $O(n)$。
  • 情况 C:$d_i = r – i$,不用尝试 / 尝试即失败

所以,Manacher 的复杂度为 $O(n)$。

相关链接

参考文章

  1. Manacher 算法
  2. Manacher’s Algorithm – Finding all sub-palindromes in $O(N)$