引入：万恶的字符串问题
你是否看到字符串就感到迷茫而无所适从？你是否看到“border”“回文”等字眼就感到大脑宕机只会暴力？如果你像我一样有这种症状，不妨一起来学习一下 Manacher 算法。
当你掌握了 Manacher 之后，你会发现，很多字符串问题都变成了板子，而你再也不用担心因为字符串抱零了……
某人：字符串有三种得分：\(0\)，\(100\)，还有无脑但不多的暴力
这么说不是在钓鱼。
某位大佬：字符串是一类很简单的困难题目。
顶级谜语人因为很多字符串问题让（尤其是像我这样的萌新）无从下手，但是如果学会了方法，你将会感觉豁然开朗，因为大多数字符串算法相比其余各种算法（比如线段树）有着较少的变形，也能较为明显地判断出来。
我们今天的 Manacher 算法就是这样一种东西，它用于求最长的回文子串（不是子序列），当然它也符合我们说的字符串算法的特征：如果你看到了一道与回文有关的题目，不妨先敲一个 Manacher 的板子，但是如果是求的其他的东西——那么就基本不用考虑 Manacher 了。
了解 Manacher
首先我们考虑怎么求出一个字符串的最长回文子串，一个非常 naive 的想法就是从第一位开始枚举，对于每一位，暴力枚举左右两边是否相同即可，这个复杂度显然是 \(\mathcal{O}(n^2)\) 的，往往不可接受，所以我们可以用 Manacher 把它的复杂度降低到 \(\mathcal{O}(n)\)。
算法流程
首先 Manacher 需要我们首先明确几个概念：
- 回文中心：就是一个回文串的最中间那个字符，我知道你可能很迷惑一个长为偶数的回文串的回文中心是哪个，不过不急，等一会。
- 回文边界：就是一个回文串最左边或者最右边的那个字符，这里我们统一考虑右边界。
- 回文半径：回文中心距回文边界的距离，这里有两种定义，一种是加上回文中心，一种是不加，我采用前者。栗子：
aaabaaa这个回文串的回文中心是b，回文半径是 \(3\) 或者 \(4\)，也正是回文半径的定义不同导致了不同的写法，但是道理都是一样的。
我们考虑如何初始化，这时我们发现了一个问题，就是暴力算法有一个小 Bug：
例如 abba，这显然是一个长是 \(4\) 的回文串，但是我们的暴力算法看起来会算成 \(0\)，为什么呢？其实问题就在于这四个字符哪个都不是回文中心，自然无法算出正确答案，这个玩意的回文中心其实是两个 b 之间的那个夹缝。
但是，奇数串就没有这样的烦恼。所以：
预处理
这就启发我们要把偶数串变成奇数串，Manacher 是这么做的：
在开头、结尾以及这个字符串的任意相邻的两个字符之间插入一个字符，以 # 为例（其实你想要什么都行，只要别和现有的重复了），也就是任何一个原字符两边都是 #。我们不难发现，对于以任意一个字符为回文中心的最长回文串，它的左右边界都是 #,那么这时任意一个回文串都是奇回文串，不信可以自己画一画手模一下。
那么我们就巧妙地解决了回文中心的问题。
接下来就是核心部分了
我们先来了解几个需要我们维护的信息：
- 一个数组 \(p_i\) 表示以 \(i\) 为中心的最长回文半径。
- 一个数 \(R\) 表示目前为止最右侧的回文右边界。
- 一个数 \(mid\) 表示 \(R\) 对应的回文中心。