Manacher 学习笔记

给定一个字符串，求该字符串的最长回文子串。

洛谷传送门

由于回文串是对称的，我们枚举对称轴（注意奇偶分类讨论）。然后从该对称轴向左向右扩展，直到两字母不相等。此时的字符串长度一定是以当前对称轴作为中心的最长回文子串。

时间复杂度$\mathcal O(n^2)$。

为了避免奇偶分类讨论，我们现在字符之间以及字符串两端插入一个特殊字符（与字符串中所有字符都不相等）。

例如：ababaab -> #a#b#a#b#a#a#b#，显然，原来是回文串的还是回文串，原来不是回文串的仍然不是回文串，长度稍做处理即可。

通过观察发现，暴力主要慢在相同的状态被重复枚举，没有利用回文串的性质。

记$hw_i$表示以$i$为对称轴时，最长的回文串的右端距离$i$（包括最右端的字符和$i$）的长度为$hw_i$。栗子：

1
2
3
4
5

char:    # a # b # a #
 hw :    1 2 1 4 1 2 1

char:    # a # b # b # a #
 hw :    1 2 1 2 5 2 1 2 1

如何快速求出$hw_i$？

考虑根据回文串的性质，利用已经求出的$hw$值来求出当前的$hw_i$。

引入两个辅助变量$MaxRight,Mid$。$MaxRight$表示当前访问到的所有回文子串，所能触及的最右一个字符的位置，$Mid$表示对应的对称轴。

为方便观察，下面的图示中记$x$为$MaxRight$关于$Mid$对称的位置，$r$表示$MaxRight$，$m$表示$Mid$，$*$表示未触及的位置。

1

| | | | |x| | | | | |m| | | | | |r|*|*|*|

当前要求$hw_i$的位置$i$一定在$Mid$右边。那么我们根据$i\le MaxRight$和$i>MaxRight$讨论：

当$i\le MaxRight$时

1

| | | | |x| | |j| | |m| | |i| | |r|*|*|*|

记$j$为$i$关于$m$的对称点。由于$hw_j$已知，我们尝试利用$hw_j$得出$hw_i$的下界。

又分成两种小情况：

$hw_j$比较小，向左没有超过$x$

大概情况如图所示：

1

| | | | |x| |-|j|-| |m| |-|i|-| |r|*|*|*|

此时显然$hw_i$的下界为$hw_j$。如图所示的情况一定也是上界，但如果$i+hw_i-1$刚好等于$MaxRight$，那么有可能可以继续扩展。由于不影响复杂度，为方便起见，无论哪一种情况都尝试扩展。

$hw_j$比较大，向左超过$x$

大概情况如图所示：

1
2
3
4
5

                    |             |
       /-------j----|--\          |
| | | | |x| | |j| | |m| | |i| | |r|*|*|*|
                   \|------i------|/
                    |             |

此时暂时只能确定两根较长的线之间的部分时回文的，所以$hw_i$的下界是$MaxRight-i+1$。然后同样地直接继续扩展即可。

实际实现中，这两种情况不需要特殊判断，只要在$hw_j$和$MaxRight-i+1$中取$min$即可。

当$i>MaxRight$时

此时显然$hw_i$的求值不能利用之前的任意值，所以定下界为$1$，也直接扩展即可。

总结

步骤

综上所述，从左到右枚举$i$的过程中，对于每个$i$，算法步骤如下：

1. 若$i\le MaxRight$，则令$hw_i=min(hw_{2*Mid-i}, MaxRight-i+1)$，否则令$hw_i=1$（显然，$i$关于$Mid$的对称点$j$为$2*Mid-i$）。
2. 以$i$为中心扩展回文串，直到左右两边字符不同，或者到达边界。
3. 更新$MaxRight$和$Mid$。
4. 更新答案。扩展出来的子串在原串中的长度一定为$hw_i-1$。因为在添加字符后的串中该子串长度为$2hw_i-1$，由于首尾一定是特殊字符，所以特殊字符数量比其他字符多$1$，所以特殊字符数量为$hw_i$，其他字符为$hw_i-1$。

一个小技巧

如果你的字符串下标从$1$开始，你可以令$s_0$为那个特殊字符，这样就省去了判断边界的问题。

复杂度分析

根据上面三种情况的分析，在继续扩展$hw_i$时，每一次的扩展都可以更新$MaxRight$，而$MaxRight$最多变化$n$次，所以总的时间复杂度为$\mathcal O(n)$的。

最长回文子串——Manacher 算法