对于一个长度为 $n$ 的回文串 $\operatorname{str}$,如果它正着读和反着读一样,即 $\operatorname{str}[i] = \operatorname{str}[n-i+1] (1 \leqslant i < n-i+1)$
如 aba
,acbbca
就是回文串,abc
,abab
就不是回文串。
$\operatorname{Manacher}$ 算法可以求出以每个位置为中心,向两边能扩展的最长回文子串长度 $p[i]$,它的时间复杂度是 $O(n)$ 的。
注意到回文子串的长度可能是偶数,如 abba
,中心不是某个字符(中心是两个 $b$ 之间的空隙),所以先要在相邻的字符中插入一个标示符,例如 #
这样例如 #a#b#b#a#
的中心就是 #
了
我们用 abbabcba
来举例。
先插入 #
得到 #a#b#b#a#b#c#b#a#
然后用 $\operatorname{Manacher}$ 可以得到如下的 $p$ 数组
对于每个 $p[i]$,一定有 $\operatorname{str}[i+j] == \operatorname{str}[i-j] ~(1 \leqslant j < p[i])$
类比 $Z$ 算法,我们也维护一个 $mx$ 和 $id$,表示对于当前计算的所有 $i$,$i+p[i]$ 的最大值是 $mx$,$mx$ 对应的 $i$ 记为 $id$ 。
当你现在开始计算 $p[i]$ 时,默认 $p[1 \cdots i-1]$ 都已经算出。
如果 $mx > i$,那么 $p[i] \geqslant \min(p[2\cdot id - i], mx-i)$
当 $mx-i > p[j]$,那么 $p[i] = p[j]$
否则 $p[i] = mx-i$,且需要进一步判断
代码实现:
int id, mx = 0;
for (int i = 1; i < n; ++i) {
if (mx > i) p[i] = min(p[2*id-i], mx-i);
else p[i] = 1;
while (s[i+p[i]] == s[i-p[i]]) p[i]++;
if (i+p[i] > mx) mx = i+p[i], id = i;
}
$\operatorname{Manacher}$ 算法的时间复杂度是 $O(n)$ 的。
考虑 $mx$ 的移动,$mx$ 最多从 $0$ 移动到 $n$,而一次字符串比较会让 $mx$ 右移一次。因此最多只会比较 $n$ 次字符相等。时间复杂度 $O(n)$ 。
原始字符串的回文字符串的长度 $= \frac{\text{预处理字符串的回文子串的长度}-1}{2} = p[i]-1$
例题:P3805 【模板】manacher 算法
代码实现:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
string s;
cin >> s;
string ns = "#";
for (char c : s) {
ns += c;
ns += '#';
}
s = ns;
int n = s.size();
vector<int> r(n);
int i = 0, j = 0;
while (i < n) {
while (i-j >= 0 and i+j < n and s[i-j] == s[i+j]) ++j;
r[i] = j;
int k = 1;
while (i-k >= 0 and k+r[i-k] < j) r[i+k] = r[i-k], ++k;
i += k; j -= k;
}
int ans = 0;
rep(i, n) {
ans = max(ans, r[i]-1);
}
cout << ans << '\n';
return 0;
}
例题: CF17E Palisection
给定一个字符串 $s$,求 $s$ 有多少对相交的回文子串,其中包含也算作相交。
如 babb
一共有 $6$ 对相交的回文子串:
s[1:1] and s[1:3]
s[1:3] and s[2:2]
s[1:3] and s[3:3]
s[1:3] and s[3:4]
s[3:3] and s[3:4]
s[3:4] and s[4:4]
$|s| \leqslant 2 \times 10^6$
分析:
统计不相交的回文子串对数。
不相交的回文子串假设端点分别为 $x_1, y_1, x_2, y_2$
那么一定有 $x_1 \leqslant y_1 < x_2 \leqslant y_2$
我们只要统计出以 $i$ 点为起点的回文串个数 $st[i]$,和以 $i$ 为终点的回文串个数。
然后计算 $\sum\limits_{i=1}^n (ed[i] \cdot \sum\limits_{j=i+1}^n st[j])$
在使用 manacher
算法的时候,对每个 $i$ 都计算出了 $p[i]$
那么我们就要把 $[i-p[i], i+p[i]]$ 这个极大回文子串对 st
和 ed
的贡献都算进去
对于 st
:$[i-p[i], i]$ 这些点每个位置都要 +1
对于 ed
:$[i, i+p[i]]$ 这些点每个位置都要 +1
只需要通过差分转化为单点修改即可。
最后用总的回文子串减去不相交的回文子串对数即是答案。