Manacher 算法学习笔记 & 详解，一文带你彻底看懂 Manacher。

凤清昶 · 4 天前

背景

给定一个字符串，请求出它的最大回文子串的长度。
第一种做法是暴力做法，也称中心扩展法。操作逻辑是我们枚举每个可能的对称中点 $i$ ，以它为中心向两边扩展，并更新答案。显然这个做法是 $\mathcal O(n^2)$ 的。
第二种做法是二分 + 哈希。通过预处理，我们可以在 $\mathcal O(1)$ 的时间内比较任意两个子串。又观察到答案具有单调性，我们再二分可能的答案一一验证。显然这个做法是 $\mathcal O(n\log n)$ 的。
但是，事实上我们有一种极为优秀的算法：Manacher 。这种做法可以做到在 $O(n)$ 时间内解决上述问题，并且编码压倒性地简单。
预处理

我们知道，回文串有奇偶之分，偶回文串不存在中心点。为了方便，我们采取一种简单的技巧统一这些情况。
具体地说，我们在每两个字符之间，以及原串的首尾分别加入一个不属于原串的字符作为分隔符（如 # ）。比如，abba 会变成 #a#b#b#a# 。显然，这并不会影响回文性质。同时，我们还在这个串的首尾额外加入两个不同的特殊字符来标记边界（如 @ 和 $ ），具体作用后文会解释。这样，原串就变成了 @#a#b#b#a#$ 。不难发现，经过这样处理，所有回文串都变成了奇回文串。后文所有讨论都基于奇回文串进行。
算法思路

Manacher 算法应用了回文串的一个重要特性：对称性。
还是需要遍历所有对称中心 $i$ 。我们定义 $p_i$ 表示以字符 $s_i$ 为中心的最长回文子串的半径，$c$ 表示目前找到的最大回文子串的对称中心，$r$ 表示目前找到的最大回文子串的右端点。由于我们进行了预处理，所以有 $ans = \max(p_i-1)$ 。问题是如何快速计算出 $p_i$ 。
中心扩展法低效的原因是有大量重复的检查。如下图，当我们已经得到了以 $s_c$ 为中心的回文，即阴影部分，当我们计算它右边的 $s_i$ 时，完全可以由已经算过的 $s_j$ 对称得到，即虚线部分。并不需要再算一次。

看起来，我们只需要一点小优化就可以了。但是，实际上并不这么简单。事实上，我们会遇到如下三种情况：
<ol>我们遍历到 $i\ge r$ ，这时以 $s_i$ 为中心的回文的镜像并不在记录范围内，其对称性是未知的。这时，我们只好先令 $p_i=1$，然后使用中心扩展法求 $p_i$ 。求完后，记得更新 $r$ 。

我们遍历到 \(ia; s = change(a); cout

账号		自动登录	找回密码
密码			立即注册

Manacher 算法学习笔记 & 详解，一文带你彻底看懂 Manacher。

相关帖子

浏览过的版块

签约作者

Manacher 算法学习笔记 & 详解，一文带你彻底看懂 Manacher。

相关帖子

相关推荐

监督微调 SFT 学习笔记

监督微调 SFT 学习笔记

监督微调 SFT 学习笔记

监督微调 SFT 学习笔记

3分钟搞懂深度学习AI：实操篇：卷积层

3分钟搞懂深度学习AI：实操篇：池化层

浏览过的版块

签约作者