【算法】Manacher 马拉车 | 最长回文串问题
twyeottk
·
·
算法·理论
1 前言
我学完这个算法的第一印象是这个算法真的很短，短到我觉得没写完。
2 Manacher 算法
2.1 概述
马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，是由 Manacher 在 1975 年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性 O(N)。
它的核心依旧是中心扩展法，它在中心扩展法上做了优化。
2.2 中心扩展法
枚举每个中心点，每次左右同时向外扩展一次，检查是否满足回文串，时间复杂度 O(N^2)。
扩展部分代码：
int len=1; // 向左右延长的长度
while (s[i-len]==s[i+len]) len++;
2.3 算法流程
首先由于回文串有中心，我们的算法需要找到中心，但是由于中心有可能在两个点中间（分数），为了避免这种情况，我们将在两个字符间插入 # 或其他原字符串中不会出现的符号来代替中心可能的分数。例如 absdf，我们将其变为 #a#b#s#d#f。
优化中心扩展法，核心是优化在每个点向左右扩展时的步数，我们就应该从一个基础值开始跳而非当前点，那么我们的目标就是找到这个基础值，这就需要分类讨论。
如图一，第一种情况，当前所在点被之前找到的回文串覆盖，因为回文串中心两侧以中心对称，所以当前点的答案应该大于等于对称点的答案。
:::align{center}
中心点
-[-[-|-]---|---[-|-]-]->
对称点 当前点
图一
:::
*图一注：中括号表示已知回文串
但是如图二，你会发现如果对称点记录的答案超过了中心点所覆盖的回文串，那么我们的答案的正确性就不能得到保证，所以面对图一和图二这两种情况，也就是已知回文串已经包括了当前点，我们要先取对称点答案，然后再看如果对称点答案加上当前点坐标超过中心点的囊括范围，那么我们就取中心点囊括范围的最右端点为临时答案。注意，这不是最终答案，我们还需要中心扩展法进一步检查。
:::align{center}
中心点
-q[a[b|c]def|fed[c|b]a]p->
对称点 当前点
图二
:::
第二种情况，那就是所有已知的中心点所囊括的范围都没有把当前点覆盖，这个时候直接用中间扩展法即可。（如图三）
:::align{center}
中心点
---[--|[-]---|---[-]|--]--->
对称点 当前点
图三
:::
所以我们总结一下，如果每个点的最长扩展长度（也就是最多同时向左右扩展多少次依旧是回文串，初始为 1）为 p_i，最大右端点为 mx，mx 所在的中心点为 id，那么当前点的临时答案为 $\text{mx} > i \ ? \ \min(p[\text{id} \cdot 2 - i], \ \text{mx} - i) : 1
值得注意的是，$p_i$ 不是最终答案，因为添加了 `#` 号，答案应该是 $p_i-1$。
### 2.4 复杂度证明
我们还是根据三个图例的三种情况来分别讨论。
首先图一的情况答案一定是固定的。
其次图二，我们现在已经把答案推到了 $mx$，再扩展一定是找到的之前没有扩展过的节点（根据右节点来说），只看图二情况最坏扩展 $N$（字符串长度）次。
图三，对于右节点一定也是没有扩展过，所以图二图三最多扩展 $N$ 次，扩展时间复杂度总共 $O(N)$，遍历每个点 $O(N)$，总共 $O(N)$。
### 2.5 代码示例
```cpp
inline vector<int> manacher(string s) {
string t="#";
for (int i=0;i<s.size();i++) {
t+=s[i],t+='#';
} s=t;
int n=s.size(); s=' '+s;
vector<int> p(n+1,0);
int id=0,mx=0;
for (int i=1;i<=n;i++) {
p[i]=mx>i?min(p[id*2-i],mx-i):1;
while (s[i-p[i]]==s[i+p[i]]) p[i]++;
if (i+p[i]>mx) id=i,mx=i+p[i];
}
return p;
}
```
## 3 例题
### 3.1 例题 —— [P3805 【模板】Manacher](https://www.luogu.com.cn/problem/P3805)
模板题，代码见上。
### 3.2 例题 —— [HDU3294 Girl's research](https://acm.hdu.edu.cn/showproblem.php?pid=3294)
模板题，注意一下字母转换即可。（**该回文串长度必须大于等于 $2$**）
字母转换代码示例：
```cpp
char get(char x,char b) {
int p='a'-b;
int w=((int(x)-'a'+p)%26+26)%26;
return char(w+'a');
}
```
### 3.3 例题 —— [P1659 [国家集训队] 拉拉队排练](https://www.luogu.com.cn/problem/P1659)
考虑到 $k$ 很大，我们可以把相同长度的使用快速幂乘起来，因为它的答案种数最多 $\frac{N}{2}+1$ 个，可以开桶记录最大答案，因为每个长度 $i$ 的回文串都可以包含一个长度 $i-2$ 回文串，所以小的回文串可以在大的回文串统计的时候得到。
```cpp
void solve() {
string s; cin >> s;
auto p=manacher(s);
vector<int> cnt(n+1,0);
int sum=0;
int ans=1;
for (int i=1;i<=n;i++) cnt[p[i]-1]++;
for (int i=n;i>=1;i--) {
if (i%2==0) continue;
sum+=cnt[i];
if (k>=sum) {
ans=(ans*qpow(i,sum))%mod;
k-=sum;
} else {
ans=(ans*qpow(i,k))%mod;
k-=sum;
break;
}
}
cout << (k>0?-1:ans) << endl;
}
```
### 3.4 例题 —— [P4555 [国家集训队] 最长双回文串](https://www.luogu.com.cn/problem/P4555)
跟上道题类似，还是可以用递推求出小的回文串，当然也可以用线段树判断重合（有点大材小用）。
这里给一下递推的代码：
```cpp
inline pair<vector<int>,vector<int>> manacher(string s) {
string t="#";
for (int i=0;i<s.size();i++) {
t+=s[i],t+='#';
} s=t;
int n=s.size(); s=' '+s;
vector<int> p(n+1,0);
vector<int> l(n+1,0),r(n+1,0);
int id=0,mx=0;
for (int i=1;i<=n;i++) {
p[i]=mx>i?min(p[id*2-i],mx-i):1;
while (s[i-p[i]]==s[i+p[i]]) p[i]++;
if (i+p[i]>mx) id=i,mx=i+p[i];
r[i+p[i]-1]=max(r[i+p[i]-1],p[i]-1);
l[i-p[i]+1]=max(l[i-p[i]+1],p[i]-1);
}
return {l,r};
}
void solve() {
string s; cin >> s;
auto [l,r]=manacher(s);
int ans=0;
for (int i=n;i>=1;i-=2) r[i]=max(r[i],(i+2<=n?r[i+2]:2)-2);
for (int i=1;i<=n;i+=2) l[i]=max(l[i],l[i-2]-2);
for (int i=1;i<=n;i++) if (r[i] && l[i]) ans=max(ans,l[i]+r[i]);
cout << ans << endl;
}
```
## 4 后记
祝您学习愉快。
### 4.1 参考资料
[【模板】manacher 题解](https://www.luogu.com.cn/article/ztshv39n) by [$\color{red}\text{Eason cyx}$](https://www.luogu.com.cn/user/741244)
[Markdown 使用帮助](https://help.luogu.com.cn/rules/academic/handbook/markdown#%E5%B1%85%E4%B8%AD%E6%8E%92%E7%89%88%E6%96%B0%E7%89%B9%E6%80%A7) by [$\color{purple}\text{洛谷}$](https://www.luogu.com.cn/)
### 4.2 更新日志
```log
2025/12/26 学习 manacher，完成一二部分
2025/12/28 补充例题，完善格式，补后记
```
---
:::align{right}
**上一章** [**【算法】AC 自动机**](https://www.luogu.com.cn/article/ecm48jk7)
**更多请见** [**专栏文章目录**](https://www.luogu.com.cn/article/zex21s0j)
:::