背景
给定一个字符串，请求出它的最大回文子串的长度。
第一种做法是暴力做法，也称中心扩展法。操作逻辑是我们枚举每个可能的对称中点 \(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\) 对称得到，即虚线部分。并不需要再算一次。
看起来，我们只需要一点小优化就可以了。但是，实际上并不这么简单。事实上，我们会遇到如下三种情况：
-
我们遍历到 \(i\ge r\) ，这时以 \(s_i\) 为中心的回文的镜像并不在记录范围内。这时，我们只好先令 \(p_i=1\)，然后使用中心扩展法求 \(p_i\) 。求完后，记得更新 \(r\) 。
-
我们遍历到 \(i<r\) ，并且 \(s_i\) 为中心的回文的镜像，即以 \(s_j\) 为中心的回文，完全在 \(s_c\) 为中心的回文内。如下图 (a) 所示。这时，显然我们可以直接令 \(p_i=p_j\) 由对称中心公式，我们知道 \(j=2c-i\) ，因此有 \(p_i=p_{2c-i}\)。显然，\(r\) 并没有被更新。
-
我们虽然遍历到 \(i<r\) ，但是 \(s_i\) 为中心的回文的镜像，即以 \(s_j\) 为中心的回文，并不完全在 \(s_c\) 为中心的回文内。如下图 (b) 所示。这时，我们并不能 \(s_c\) 为中心的回文以外的部分的对称性，不能贸然地令 \(p_i=p_j\) 。事实上，我们只能先令 \(p_i = w = r-i\) （这部分的对称性是可以保证的）然后再使用中心扩展法得到正确的答案。求完后，同样记得更新 \(r\) 。
以上第 \(2,3\) 种情况可以一起处理，即 \(p_i=\min(p_{2c-i},r-i)\) ，然后统一用中心扩展法。
复杂度
以上的流程，虽然看着在频繁地使用中心扩展法，好像复杂度很高；但事实上，上述流程的实质是在扩展 \(r\) 。随着 \(r\) 的增大，情况 \(2\) 出现的比重越来越大，调用中心扩展的次数也越来越少。同时，每使用中心扩展法迭代一次，\(r\) 一定能增大 \(1\) ，而 \(r\) 的上界就是字符串长度 \(n\) 。因此，这个算法是 \(\mathcal O(n)\) 的。
代码实现 & 模板题
Luogu P3805 【模板】Manacher
代码如下：
#include<iostream>
#include<string>
#include<cstring>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MIKU 0
using namespace std;int t;
int p[22000010];
string a, s;string change(string s) { //预处理string res;res += "@#";for(char ch : s) res += ch, res += "#";res += "$"; //首尾置不同字符，防止中心扩展越界return res;
}int Manacher(string s) { //核心memset(p, 0, sizeof(p));int c = 0, r = 0, ans = 0, len = s.size();for(int i=0; i<len; i++) {if(i < r) p[i] = min(p[c*2-i], r-i); //情况 2,3 的合并else p[i] = 1;while(s[i+p[i]] == s[i-p[i]]) p[i] ++; //中心扩展if(p[i] + i > r) r = p[i] + i, c = i;ans = max(ans, p[i]-1);}return ans;
}int main() {fastio;cin>>a;s = change(a);cout<<Manacher(s);return MIKU;
}