Manacher 马拉车
定义
Manacher 马拉车，一种为了求字符串中最长的回文字串的算法。
暴力
这个算法是从暴力的方法转化过来的，暴力肯定是枚举字符串每个字符作为中心，然后向外扩展，这样的复杂度为 \(O(n^2)\)。
特殊处理
而 Manacher 则是按照回文对称的性质的进行优化的，首先回文串有奇数串 \(aba\) 和偶数串 \(abba\) 如果直接对原串进行操作会有些复杂，所以可以将每个字符之间用 # 隔开，最开头结尾要用更特殊的两个不同字符表示边界，这样这个字符串就必定变为一个长度为奇数的字符串，这样就好进行操作。
void change(){
cin>>a;
n=a.size();
s[0]=s[1]='#';
for(int i=0;i<n;i++){
s[i*2+2]=a[i];
s[i*2+3]='#';
}
n=n*2+2;
s[n]='&';
}
引入半径数组
下一步我们用 \(hw[i]\) 表示以 \(i\) 为中心的回文串的半径，如 \(\&\#a\#b\#a\#\%\) 中 \(b\) 为下标为3，则 \(hw[3]=4\)(半径表示：\(b\#a\#\))，然后就发现回文长度就好像是半径长度减一(好神奇)，因为引入了 # 就相当于另一边相等的字符可以补充过来（我在讲什么，感性理解一下吧）。
但为什么要减一呢？因为有时可能回文中心为 \(\#\) 有时可能半径边界为 \(\#\) 但这些 \(\#\) 为无效补充（没有其他字符可以补充）。
综上所述，只要算出每个字符的 \(hw[]\) 然后求最大值就可以了。
求出半径数组
好！接下来就是快速求出 \(hw[]\) 了，接下来我们用 \(mr(maxright)\) 表示我们遍历过最靠右的点，用 \(mid\) 表示这个点的对称中心，然后我们就可以发现不是每个点都必须要遍历一遍，可以依靠对称的性质，下面开始分类讨论。
分类讨论
1. i未超过mr
l：r 关于 mid 的对称点
如果 j 的最长回文没超过 l 那么有 \(hw[i]=hw[j]=hw[mid-(i-mid)]=hw[mid*2-i]\)
但要是超过的话就不一定了具体多长，但最起码 \(j-l(r-i)\) 那段长度一定是回文的，然后不确定的长度要暴力更新。
2. i超过mr
这时没有遍历过，所以一切都是未知的，就只能暴力枚举然后更新 \(mr\)。
总结
这样就遍历完全部的 \(hw[]\) 了，因为 \(mr\) 总是向右更新的所以时间复杂度均摊为 \(O(n)\)，其实可以用 devc++ 的 GDB 调试自己跑一遍看看过程，很有作用的。
代码模板
#include<bits/stdc++.h>
using namespace std;
string a;
int n,ans=1;
char s[40000005];//注意开大点
int hw[40000005];//大点
void manacher(){
int mr=0,mid;
for(int i=1;i<n;i++){
hw[i]=1;
if(i<mr){
hw[i]=min(hw[(mid<<1)-i],mr-i);//注意取min，可以感性理解下
}
while(s[i+hw[i]]==s[i-hw[i]]){
++hw[i];//暴力扩展
}
if(hw[i]+i>mr){//更新mr
mr=hw[i]+i;
mid=i;
}
}
}
void change(){
cin>>a;
n=a.size();
s[0]=s[1]='#';//边界
for(int i=0;i<n;i++){
s[i*2+2]=a[i];
s[i*2+3]='#';
}
n=n*2+2;
s[n]='&';//边界
}
int main(){
ios::sync_with_stdio(false);
change();
manacher();
for(int i=0;i<n;i++){
ans=max(ans,hw[i]);//每个都有可能
}
cout<<ans-1;//注意减一
return 0;
}
例题讲解
1.神奇项链
51nod 3117
题意
这题很适合入门马拉车，但需要学习前置知识线段完全覆盖问题（不会只有我做这题的时候还要现学，菜）。
先翻译题意吧，给出一个字符串，问这个字符串由几个回文字串拼成，如果两个回文串拼接前缀和后缀相同就可以将这个重复部分重叠。
↑翻译的好烂，有能力还是看原文吧↑
解析
可以用 manacher 求出每个数的回文半径，然后对于每个回文中心都会有一段区间，然后问题就转化为线段完全覆盖问题了，然后套板就好。
解析
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
char a[1000005];
int hw[1000005];
struct ss{
int l,r;
}b[1000005];
bool cmp(ss g,ss h){
if(g.l!=h.l){
return g.l<h.l;
}
else{
return g.r<h.r;
}
}
void manacher(){
int mr=0,mid;
for(int i=1;i<n;i++){
hw[i]=1;
if(i<mr){
hw[i]=min(hw[(mid<<1)-i],mr-i);
}
while(a[i+hw[i]]==a[i-hw[i]]){
hw[i]++;
}
if(hw[i]+i>mr){
mr=i+hw[i];
mid=i;
}
}
}
void change(){
a[1]=a[0]='#';
for(int i=0;i<n;i++){
a[i*2+2]=s[i];
a[i*2+3]='#';
}
n=n*2+2;
a[n]='&';
}
int main() {
ios::sync_with_stdio(false);
int k;
cin>>k;
while(k--){
cin>>s;
n=s.size();
change();
manacher();
n-=1;//我喜欢写 i<=n，个人习惯问题。
//排除 # 的点
for(int i=1;i<=n;i++){
hw[i]-=1;
}
//求出区间
for(int i=1;i<=n;i++){
b[i].l=i-hw[i];
b[i].r=i+hw[i];
}
//线段完全覆盖问题板子
sort(b+1,b+n+1,cmp);
int ml=b[1].r,mr=b[1].r,ans=0;
for(int i=1;i<=n;i++){
mr=max(mr,b[i].r);
if(b[i+1].l>ml){
ml=mr;
ans++;
}
}
cout<<ans-1<<"\n";//是拼接所以要减一
}
return 0;
}