学习心得 - 字符串 - Manacher

ExFish · 2025-01-21 15:36:05 · 算法·理论

更好的表述：https://www.luogu.com.cn/article/acf4low9

问题

长度为 n 的字符串 s，找出所有回文子串的个数 / 最长长度。

这类字符串问题，常用 Manacher 算法。

解法

字符串哈希：\mathcal O(n\log n)。

SA、快速 LCA：\mathcal O(n)。

朴素解

考虑使用中心扩展法。

每一次确定了中间的字符，然后向左右两侧扩展枚举，求出 len \mod 2=1 的回文子串。

对于中间的字符，考虑一个指针多一，就可以求出 len \mod 2=0 的回文串。

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

改动 1

考虑在相邻字符加入 #（包括左右），左侧再加入 $，右侧 &，就可以将偶数回文串转为奇数回文串。

例子

原串 / 修改后：

a b b a
$#a#b#b#a#&

Manacher

我们定义 p_i 为 i 开始的最长回文半径。

上面的例子就是 p_i=\{1,1,2,1,2,5,2,1,2,1,1\}。

那么最长的就是 \max p_i-1。

例如 p_5=5，对应原串 #a#b#b#a#，回文长 p_5-1=4，abba。

同样易得，这个回文串的开头在 \lfloor\frac{i-p_i}{2}\rfloor。

我们的问题，转换成了如何高速求解 p_i。

Manacher 的核心思想：回文的镜像也是回文。

我们来优化朴素解：减少重复的检查。这不就是 KMP 和 AC 自动机的优化朴素解方法吗。

如图，这里显示了 Manacher 更优的原因——这样，我们在处理 s_j 的时候就可以直接用 s_i 的值，从而减少检查次数。（回文镜像原理）

但是，\bold{p_j>p_c} 时，\bold{p_i\neq p_j}，出错。

像这样的问题还有几个，所以接下来介绍实现。

算法设计

动态规划。

我们设当前要求 p_j。

令回文串最大右端点 r，它是 p_k 的右端点，r=k+p_k。

• - 镜像 $j(i)$ 不超过 $r$，$p_j=p_i=p_{2k-j}$。**（回文镜像原理）** - 镜像 $j(i)$ 不被 $k$ 包含，则限制失效，$p_j=w=r-j=k+p_k-j$，只能暴力扩展。

情况可以一起处理，p_j 取最小值。

例题就模板，复杂度 \mathcal O(n)，太 6 了。

参考资料：Manacher，算法竞赛。