Manacher算法，又名“马拉车”算法。
引入
给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 $s$ ,求 $s$ 中最长回文串的长度 。
对于这种问题，一眼便有两种朴素算法。
-
枚举最长回文串的左右边界 $l,r$，然后 $\mathcal O(r-l+1)$ 判断回文。
时间复杂度：$\mathcal O(n^3)$。
-
枚举回文串的中心 $s_i$，然后从 $s_i$ 开始向两边扩展。即：判断 $s_{i-1},s_{i+1}$ 是否一样，$s_{i-2},s_{i+2}$ 是否一样，$s_{i-3},s_{i+3}$ 是否一样，直到 $s_{i-k},s_{i+k}$ 不一样时便可以得出以 $s_i$ 为中心的最长回文串长度。
时间复杂度：$\mathcal O(n^2)$。
令 $s$ 长度为 $n$。
当 $n$ 超过 $2\times10^4$ 时，$\mathcal O(n^2)$ 的算法便很难在 $1s$ 内得出答案，考虑使用其他方法。
- 字符串哈希，$\mathcal O(n\log_2n)$。
- 后缀数组+快速LCA，$\mathcal O(n)$。（使用加减 1RMQ求解欧拉序+ST表的LCA，可以做到 $\mathcal O(n)$ 预处理，$\mathcal O(1)$ 查询）
然而，这些算法都不是那么的简单，相比起来这些，Manacher算法 是 压倒性 的简单。
但是这里描述的算法 压倒性 的简单，并且在时间和空间复杂度上具有更小的常数。该算法由 Glenn K. Manacher 在 1975 年提出。——OI Wiki
Manacher算法实现
回文转化
首先，回文分为奇回文和偶回文。对于这两种情况的回文中心，明显需要分类讨论。
考虑转化，那么我们在每两个相邻字符之间插入一个特殊字符即可。
- 对于奇回文，回文中心不变。
- 对于偶回文，回文中心便是我们插入的特殊字符。
比如：abcba 变为 a#b#c#b#a，原先回文，现在仍然回文；abccba 变为 a#b#c#c#b#a，原先回文现在仍然回文，但是从偶回文转变为了奇回文，回文中心为插入的 #。
回文中心与回文半径
-
首先，回文串是关于回文中心呈轴对称的。
- 在一个回文串 $s$ 内选一子串 $t$，那么在 $s$ 内一定还存在一个子串 $t’=rev(t)$，$rev(t)$ 表示 $t$ 的反转字符串。
- 如果回文串 $s$ 的左半部分有子串 $s_1$ 回文，那么右半部分也一定存在子串 $s_2$ 回文，且满足 $s_1=rev(s_2)$。
考虑记录以 $s_i$ 为回文中心的最长回文半径（包括 $s_i$） $p_i$。
例如对于 a#b#a，b 的回文半径就是 $3$。
状态转移
令插入后的字符串 $s$ 长度为 $m=2n+1$。
令 $r$ 为当前已确定的、最远的回文串右边界。即：$r=\max \limits_{i=1}^m(i+p_i-1)$。
令 $mid$ 为当前已确定的、最远的回文串回文中心。
令字符串 $a$ 是 $s$ 插入后的字符串，从下标为 $1$ 开始存储。
对于 $i$ 遍历 $1\sim m$，若 $i<r$，都可以确定：
\[\large p_i\geq \min\left(p_{2\times mid+1},r-i+1\right)\]首先，取最小值是为了防止越出 $r$ 的范围，很好理解。
对于 $p_{2\times mid+1}$，如图：
其中 $j$ 为 $i$ 关于 $mid$ 的对称点，也就是 $j=2\times mid-i$。
那么以 $j$ 为中心的最长回文串（$\color{#FF7F27}\colorbox{#FF7F27}{1}$ 橙色部分）也是关于 $mid$ 对称，则 $\color{#ED1C24}\colorbox{#ED1C24}{1}$ 红色部分同样回文且其为 $\color{#FF7F27}\colorbox{#FF7F27}{1}$ 橙色部分的反转字符串（事实上，一个回文字符串无论如何反转，都是不变的，也就是说，两部分其实是全等的）。
那么 $p_i$ 就可以直接赋值为 $\min\left(p_{2\times mid+1},r-i+1\right)$，然后再进行暴力向两边扩展的操作即可。
统计答案
令 $ans=\max_{i=1}^mp_i$，则最长回文串的长度为 $ans-1$，理由如下：
首先， $ans$ 中是记录了 插入字符（#）的个数。
-
$ans$ 以
#为中心的时候。明显长这样：
#a#a#a...a#a...a#a#a#；a可以替换为任意字符，但要求回文；...表示省略。那么半径上的有效字符（非
#）个数为：$\frac{ans-1}{2}$。整个回文字符串长度为：$2\times\frac{ans-1}2=ans-1$。
-
$ans$ 不以
#为中心的时候。明显长这样：
#a#a#a...a#a#a...a#a#a#；a可以替换为任意字符，但要求回文；...表示省略。那么半径上的有效字符（非
#）个数为：$\frac{ans}{2}$。整个回文字符串长度为：$2\times\frac{ans}2=ans$。考虑到回文中心计算了两次，则最终答案为 $ans-1$。
故答案为 $ans-1=\left(\max\limits_{i=1}^mp_i\right)-1$。
时间复杂度分析
虽然套了两层循环，但是仍为 $\mathcal O(n)$。
首先最外层循环遍历 $[1,m]$ 肯定是 $\mathcal O(m)=\mathcal O(2n+1)=\mathcal O(n)$。
那么考虑 while() 的总数到底是多少：由于匹配过的位置不再匹配，且最坏情况下 $r$ 每次自增 $1$，那么每个字符至多匹配一次，$\mathcal O(m)=\mathcal O(2n+1)=\mathcal O(n)$。
故，总时间复杂度为 $\mathcal O(n)$。
边界条件
我们可以令 $a_0$ 为 ~（不同于插入的 # 和其他有效字符）。
这样是为了防止越界。
注意到，只有 while(a[i-p[i]]==a[i+p[i]])p[i]++; 可能会产生越界，那么我们令 $a_0$ 为一个不同于 $a_{2i}$ 的值即可。
例题AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1.1*1e7;
int n,m,p[2*N+1];
char s[N+1],a[2*N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%s",s);
n=strlen(s);
a[m]='~';
for(int i=0;i<n;i++){
a[++m]='#';
a[++m]=s[i];
}a[++m]='#';
int ans=0;
for(int i=1,r=0,mid=0;i<=m;i++){
if(i<=r)p[i]=min(p[mid*2-i],r-i+1);
while(a[i-p[i]]==a[i+p[i]])p[i]++;
if(p[i]+i>r)r=p[i]+i-1,mid=i;
if(p[i]>ans)ans=p[i];
}printf("%d\n",ans-1);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
