Manacher算法
形象的被译为马拉车算法
这个算法用于处理简单的回文字符串的问题。可以在 \(O(n)\) 的复杂度内处理出每一个位置为中心的回文串的最长长度。
为了避免出现偶数长度的回文串，导致过多的分类讨论，我们预处理一下字符串。
例如：jeefy
我们可以预处理成 ^#j#e#e#f#y#$。（开始，间隔和结束符尽量不一样，并且不能出现在原序列中）
那么我们再定义一点点东西：
-
P[i]指在处理后的字符串中，以i为中心的回文串的最大长度的半径（包括了i）也就是说，处理后的串中，(i-P[i], i+P[i])这个开区间是一个回文串。 -
R指我们已经搜索到的最右边界，M指最右边界对应的中心
为了方便讲解，我们先考虑更朴素的算法：中心扩展法（名字来源LeetCode）。
其实思路很简单，我们以某一个点为中心，向两边扩展，同时需要分类讨论奇数长度和偶数长度。
int expandAt(char * s, int l, int r) {
int len = strlen(s);
while (0 <= l && r < len && s[l - 1] == s[r + 1]) ++r, --l;
return r - l + 1;
}
未验证代码，注意甄别
其时间复杂度为 \(O(n^2)\) ，但是，在随机数据下，其表现接近于线性。毒瘤出题人当然不愿意了
所以，有了Manacher算法来优化。
其算法核心思想在于利用回文串的对称性，这样我们可以充分的利用其对称区间的信息。
如图：
若黑色区间是一个回文串，且黑色竖线为其中心，已知红色区间是一个能向外扩展的最长回文串，那么很容易得知橙色的区间也是一个回文串，并且这个回文串对于这个中心是最长的。
理解回文串的对称性，如果橙色的不是最长的，意味着对称过来红色的也不是最长的，与已知冲突。
那么我们考虑什么时候可以扩展出去？
如图，如果左侧对应的回文串左边界超过或者等于黑色部分的边界，那么，实际上，右侧只有橙色部分（黑色边界内）的信息是可以用的。
因为回文串的对称性并没有包括了黑色部分以外的信息，所以……
同理，如果右侧的中心已经在黑色部分以外了……那么也没有可用的信息，暴力扩展即可。
参考代码：
for (int i(1); i < n; ++i) {
p = R > i ? min(R - i + 1, P[(M<<1) - i]) : 1; // 可用信息
while (s[i + p] == s[i - p]) ++p; // 向两边扩展
if (i + p - 1 > R) M = i, R = i + p - 1; // 更新边界
P[i] = p;
}
复杂度证明：
我们考虑边界 R，从 0 更新到 n，总共变化了 n 次。
那么 R 什么时候被更新？
也就是第二种情况，可以向外扩展才可以更新 R，且每一次成功的扩展会使 R 变大一位。
如果是第一种情况，那么是无法向外扩展的，且 R 也不会改变。
也就是说，最多只会扩展 \(O(n)\) 次，所以，整个算法的复杂度为 \(O(n)\)，常数非常小。
对于模板题：【模板】manacher 算法 - 洛谷
参考代码如下：
