从某种方面来说，Manacher 算法是朴素 \(O(n^2)\) 暴力算法的优化。。。
那就得先了解一下 Manacher 的朴素算法------
朴素算法
枚举中心点并不断向外展开（例如：\([i,i]\rightarrow [i+1,i+1]\rightarrow [i+2,i+2]\rightarrow \dots\)）
缺点：
- 时间复杂度：\(O(n^2)\)，慢
- 不能处理长度为偶数的回文串，菜
Manacher
想要优化，首先得解决几个问题：
如何处理长度为偶数的回文串？
可以这样：在每个字符串间及开头结尾加上一个特殊字符（例子：aaaa $\rightarrow $ ~#a#a#a#a#）
考虑例子中为什么开头第一个地方有个 ~ ？
这个后面代码中再说（防止数组越界）。。。
如何使时间复杂度降到线性？
记录一个数组p[i]表示以 \(i\) 为回文中心的回文半径。
现在就是处理来到 \(i\) 这个点，如何转移p[i]？
我们在这里维护一个当前回文串最右端点 \(r\)，和其对称中心 \(mid\)。
当 \(i\le r\) 时
因为 \(i+p[i]-1\le r\)
所以 \(p[i]\le r-i+1\)
我们通过以 \(mid\) 为对称轴得到一个与当前的 \(i\) 对称的点 \(j\)（这个对称点点的p[]已经处理出来）来转移p[i]，同时还能向外扩展：while(s[i-p[i]]==s[i+p[i]])++p[i];
求 \(j\) 就用初一的中点公式：\(\frac{i+j}{2}=mid\rightarrow j=2*mid-i\)
所以 \(p[i]=min(p[2*mid-i],r-i+1)\) 。
当 \(i>r\) 时
\(p[i]=1\)，就是不能向外扩展（只有自己本身的长度）。
板子代码：
#include <bits/stdc++.h>
using namespace std;
const int N=3e7+5;
int n,p[N];
char s[N],st[N];
int cnt=1;
void init()
{
s[0]='~';
s[cnt++]='#';
for(int i=0;i<n;i++)
{
s[cnt++]=st[i];
s[cnt++]='#';
}
}
int main()
{
cin>>st;
n=strlen(st);
init();
int ans=-1;
for(int i=1,r=0,mid=0;i<=cnt;i++)
{
if(i<=r)p[i]=min(p[2*mid-i],r-i+1);
while(s[i-p[i]]==s[i+p[i]])++p[i];//解释一下：s的第一位那个~，就是在while循环中防止越界
if(i+p[i]>r)r=p[i]+i-1,mid=i;
if(ans<p[i])ans=p[i];
}
cout<<ans-1;
return 0;
}