【学习笔记】字符串—马拉车（Manacher）
辰星凌
·
·
个人记录
【学习笔记】字符串—马拉车（Manacher）
一：【前言】
马拉车用于求解连续回文子串问题，效率极高。
其核心思想与 kmp 类似：继承。 ——引自 yyx 学姐
二：【算法原理】
对于任意一个回文串 a，设其中点为 mid（为方便描述，偶数串则在正中央加一个位置），那么根据定义，有：
a[mid-1]==a[mid+1]
a[mid-2]==a[mid+2]
...
可知：
如果 a[mid-x] 可以形成半径为 r 的回文串，且不越过以 mid 为中心的回文串，那么 a[mid+x] 也可以形成半径为 r 的回文串。
以奇回文串为例，用 r[i] 表示以 i 为中点的最大回文串长度。
如果我们已知 r[mid],r[j](j \in [mid-r[mid]+1,mid-1])，那么可以分两种情况推出其关于 mid 的对称点 i (\frac {i+j}{2}=mid) 的半径：
设 R=mid+r[mid]-1 。
$(2).$ $i+r[j]-1>R,$ $r[i]=R-i+1$ 。
即 $r[i]=min(r[j],R-i+1)$ 。
如上所述，实现了从前面信息到后面信息的**继承**。
**继承**之后还需要判断以 $i$ 为中心能否继续扩张，这时候可以直接**暴力枚举扩大半径**。
------
## **三：【算法实现】**
实时维护一个已知**覆盖范围最靠右**的回文串信息，记录其中点 $mid$ 和右端点 $R$。
从 $1,n$ 枚举 $i$：
若 $i<=R$ 则可以用 $i$ 的对称点 $mid*2-i$ 得到 $r[i]$，
若 $i>R$（即 $R=i-1$ 的情况，因为 $R$ 永远大于等于 $i-1$），初始化 $r[i]=1$，然后暴力扩大求出最大 $r[i]$。
如果以 $i$ 为中点可以得到**更靠右**的回文串，更新 $mid$ 和 $R$。
但偶数串不太好处理，所以在原字符串中的所有空隙中插入一个不可能出现的字符，例如 $'*',$ $'|'$ 等等，最前面和最后面也要插。
此时，**奇数串还是奇数串**，**偶数串则变成了奇数串**，可以统一按照奇数串处理啦。
**注意：统计答案时应取真实的回文串长度。**
（具体可以自己画个图分类讨论一下，会发现无论奇偶，无论是否为原字符串中的字符，$r[i]-1$ 始终等于以 $i$ 为中点的实际最大回文串长度。）
#### **【Code】**
题目：[$Palindrome$ $[Poj3974]$](http://poj.org/problem?id=3974)
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
#define Re register int
using namespace std;
const int N=1e6+5;
int n,R,mid,ans,OOO,r[N<<1];char op[N],a[N<<1];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
while(cin>>op){
if(op[0]=='E'&&op[1]=='N'&&op[2]=='D')break;//没用string就只能这样一位一位地判断了
a[0]='$',a[n=1]='*',R=0,mid=0,ans=0;
for(Re i=0;op[i];++i)a[++n]=op[i],r[n]=0,a[++n]='*',r[n]=0;//玄学填空法
for(Re i=1;i<=n;++i){
r[i]=i<=R?min(R-i+1,r[(mid<<1)-i]):1;//继承前辈的信息
while(a[i-r[i]]==a[i+r[i]])++r[i];//暴力扩张领域
if(i+r[i]-1>R)R=i+r[mid=i]-1;
ans=max(ans,r[i]-1);//取实际回文长度
}
printf("Case %d: %d\n",++OOO,ans);
}
}
```
------
## **四：【时间复杂度】**
似乎看起来效率并不高，近似 $O(n^2)$，但实际上它的理论复杂度是 $O(n)$。
为何？
对于每个 $i$：
如果 $i<=R$，那么直接 $O(1)$ 计算 $r[i]$。
如果 $i>R$，那么会用 $O(len)$ 向右扫描 $len$个单位，所以此时 $R$ 会向右移动 $len+1$ 的单位。
而 $R$ 最多只会移动 $n$ 个单位，因此 $Manacher$ 算法时间复杂度是线性的：$O(n)$。
------
## **五：【例题】**
- [【模板】$manacher$ 算法 $[P3805]$](https://www.luogu.org/problem/P3805)
【标签】字符串/回文串/$Manacher$ 模板
- [$Palindrome$ $[Poj3974]$](http://poj.org/problem?id=3974)
【标签】字符串/回文串/$Manacher$ 模板/$Hash$/二分
- [$Palindrome$ $pairs$](https://www.luogu.org/problem/CF159D) [$[CF159D]$](http://codeforces.com/problemset/problem/159/D)
【标签】字符串/回文串/$Manacher$/差分
【题解】[$Xing$_$Ling$](https://www.luogu.com.cn/blog/ChenXingLing/solution-cf159d)
- [$Sonya$ $and$ $Matrix$ $Beauty$](https://www.luogu.org/problem/CF1080E) [$[CF1080E]$](http://codeforces.com/problemset/problem/1080/E)
【标签】字符串/回文串/$Manacher$/暴力枚举/整体思想
【题解】[$Xing$_$Ling$](https://www.luogu.com.cn/blog/ChenXingLing/solution-cf1080e)