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

背景

给定一个字符串，请求出它的最大回文子串的长度。
第一种做法是暴力做法，也称中心扩展法。操作逻辑是我们枚举每个可能的对称中点 \(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