【算法漫笔005】Manacher

FeIndentOvO

2026-08-25 14:53:55

发布于：重庆

11阅读

0回复

0点赞

笑点解析：我最终还是更新了 Manacher。

【算法漫笔005】浅谈Manacher

Manacher 算法用于解决查找最长回文子串问题（下文令操作的字符串 $S$ 的长度为 $N$ ），时间复杂度为 $O(N)$ 。

Brute Force

即暴力拓展法。寻找 $S$ 中的回文子串，很容易想到暴力匹配。我们遍历 $S$ 的每一个字串，检查正读反读是否一样，取最大值即可。时间复杂度为 $O(N^3)$ ，期望 $N \le 5 \times 10^2$

Center Expansion

即中心拓展法。分两种情况，即奇回文和偶回文。奇回文遍历 $S$ 的每一个字符，从该字符向外拓展，找到不同的即不是回文子串，否则继续向外拓展至边界或两边字符不相同为止。其时间复杂度显然为 $O(N^2)$ ，期望 $N \le 10^4$ 。

Manacher

容易发现，Center Expansion算法仍然有许多可以优化的地方，例如：奇回文和偶回文需要单独计算、时间复杂度过高等问题，Manacher将一一解决这些问题。

统一奇偶回文

我们尝试在 $S$ 的每两个字符之前插入一个 #^[1]，并在头尾也插入一个 #，得到新字符串 $T$ 。例如我们令 $S=abc$ ，则 $T=\text{"\#a\#b\#c\#"}$ 。

显然，此时原串中的任意回文子串都会在 $T$ 中对应一个奇数长度的回文串：

奇回文 aba 对应 #a#b#a#，中心是 b。
偶回文 abba 对应 #a#b#b#a#，中心是 #。

这样我们就成功的统一了奇偶回文。那么时间复杂度怎么处理呢？

回文半径数组

我们定义一个 $p_i$ 表示以 $T_i$ 为中心的最长回文半径^[2]。例如 $T=\text{"\#a\#b\#a\#"}$ ，则有 $p_3=4$ ，即 $T$ 本身。显然我们只需要计算出回文半径数组 $p$ ，那么 $res=\max(p_0,p_1 \dots p_{T_{len}})$ 的值就是 $T$ 的最长回文串长度，而 $S$ 的最长回文串长度显然是 $res-1$ 。所以问题就转化成了：如何快速计算 $p_i$ ？

快速计算 $p_i$

直接对每个 $i$ 暴力扩展，时间复杂度显然是 $O(N^2)$ ，没有改进。而 Manacher 的核心就是利用的回文的对称性，避免重复扩展。

简单来说，如果一个奇回文串的长度 $\ge 3$ 的话，那么它一定可以分成 $L+c+R$ ，其中 $c$ 是若干个字符，而 $L$ 和 $R$ 是两个长度相等的子串，且 $R$ 是 $L$ 的逆序。

不难想到，如果我们已经知道了一个较大的回文串，那么它内部的所有位置都可以利用对称性快速得到回文半径的下界，而不需要重新暴力扩展。

我们维护两个变量 $r$ 和 $mid$ ，分别表示当前所有回文串中，最靠右的右端点（即 $i+p_i$ 的最大值）和其对应的回文中心。此时如果要计算 $p_i$ ，我们可以分两种情况讨论。

① $i<r$

此时 $i$ 被某个已知的大回文串覆盖。找到 $i$ 关于 $mid$ 的对称点 $j=2\times mid-i$ 。由于回文的对称性，所以 $T_j$ 附近的回文情况一定可以反映到 $T_i$ 附近，但不能超出大回文串的边界 $r$ ，因此得到：

$p_i=\min(p_j,r-i)$

② $i \ge r$

此时无法利用任何信息，我们只能令 $p_i=1$ 。

此时我们就可以从上述得到的 $p_i$ 开始，继续暴力向两边 Center Expansion。

拓展后若 $i+p_i>r$ ，我们就可以更新 $r=i+p_i$ 和 $mid=i$ 了。

时间复杂度证明

Manacher 算法的核心思路类似于 exKMP（点我），时间复杂度的证明也类似。

首先：我们需要关注算法中唯一可能带来额外开销的部分，即 while 暴力 Center Expansion 的部分。

关键在于观察到， $r$ 在我们整个算法过程中是单调不减的。

当 $i<r$ 时， $p_i$ 被初始化为 $\min(p[j],r-i)$ ，这保证了我们不会在已知的大回文串内部进行重复的无效扩展。
随后的 while 循环每成功匹配一次，都会使以 $i$ 为中心的回文串向右扩展一位。因为 $i$ 是固定的，这必然导致当前最右端点 $i+p_i$ 向右移动，也就是更新了 $r$ 的值，使其至少增加 1。
由于 $r$ 的最大值不会超过新串 $T$ 的长度 $2N+1$ ，所以整个算法过程中，while 循环的总执行次数是 $O(N)$ 的。

因此，外层循环遍历 $T$ 的每个位置是 $O(N)$ ，内层 while 循环的总次数也是 $O(N)$ ，故 Manacher 算法的总时间复杂度为 $O(N)$ 。

于是我们就得到了 $O(N)$ 求最长回文子串问题的算法了。

恭喜你水了一道青题。

洛谷P3805

/*
Code from:
Luogu FeIndent
Becoder c2028hf2
ACGO FeIndentOvO
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1e6+5;
string s,t;
int p[N*2];
int manacher() {
	int n=s.size();
	t+='^';
	for (int i=0;i<n;i++) {
		t+='#';
		t+=s[i];
	}
	t+='#';
	t+='$';
	int mx=0,id=0;
	int ans=0,len=t.size();
	for (int i=1;i<len-1;i++) {
		if (i<mx) {
			p[i]=min(p[2*id-i],mx-i);
		}
        else {
			p[i]=1;
		}
		while (t[i-p[i]]==t[i+p[i]]) {
			p[i]++;
		}
		if (i+p[i]>mx) {
			mx=i+p[i];
			id=i;
		}
		ans=max(ans,p[i]);
	}
	return ans-1;
}
int main() {
	cin >> s;
	cout << manacher();
	return 0;
}