【7】Manacher 学习笔记

~~谔谔把题解粘过来水一篇笔记（雾~~

\Large\textup{\bf{Part 1 : 算法介绍}}

Manacher，是一种用于求解字符串中最长回文串的算法。它可以在

O(n)

的时间里求出以每一个字符为中心的回文串最大长度。

\Large\textup{\bf{Part 2 : 算法流程}}

下记

p_i

为以第

i

个字符为中心的回文串最大长度。例如，ababa 的长度是 $3$ 。

下面所说的“暴力计算”均指如下代码（假设当前在

i

，需要暴力计算

p_i

）：

CPP

while(s[i+p[i]] == s[i-p[i]]) p[i]++;

首先处理一个问题：有些回文串长度是偶数，有些是奇数。奇数可以枚举中心点；但是偶数不行！为了解决这个问题，我们可以在所有字符之间插入一个 #，这样偶回文串就被我们转换成了奇回文串了。

考虑当前需要求出

p_i

。我们可以记录一个

r

，用来表示在所有

1 \le j < i

的

j

中，以

j

为中心点的回文串的右端点中，最右的那一个。记这个

r

为右端点的回文串的中心点为

j'

。此时我们需要进行分类讨论：

$r>i$

此时我们可以得到下图：

这个图是什么意思？我们首先可以找到

i

以

j'

为对称中心的对称点

i'=j'\times2-i

。然后，因为这一整个是一个回文串，所以对应地，

i'

下面那一段（指那一段子串）和

i

下面那一段一定也相同。所以在这种情况下，

p_i=p_{i'}

，可以直接得出！

但是！情况不一定总是这么好。在

r>i

的情况中，还有另外一种情况：

如图，当

p_{i'}

很大的时候，这一段可能超出了整个大回文串，当这个子串对称到以

i

为中心的这边时，右端点超过了

r

，而超出的部分我们一无所知！在这种情况下，我们不能保证

i

的回文长度一定有这么长，只能保证从

i

到

r

这一段一定回文。所以，在这种情况下，我们可以令

p_i=r-i

，然后暴力向外计算

p_i

的最终值。稍后我们会说明这样是对的。

这样，

r>i

的情况暂时被我们解决了。

在每次更新完

p_i

后，注意要实时更新

r

和

j'

，用来计算后面的答案。

$r<i$

此时的情况如图：

此时可以很清晰地看出，没有任何可以使用的信息，所以只能暴力计算

p_i

了。此时也需要更新

r

。

遍历

1 \sim n

重复如上过程，即可得到所有

p_i

。因为在计算之前在字符串中还插入了一些 #，所以最终答案其实就是

\max p_i-1

。

\Large\textup{\bf{Part 3 : 正确性证明}}

首先正确性是显然的。

对于复杂度，我们可以感性理解一下：在上面的三种情况中，第一种是

O(1)

的；后两种都在不断地将

r

向后推，而一共只有

n

个位置；所以总的时间复杂度就是

O(n)

。

\Large\textup{\bf{Part 4 : 例题讲解}}

P3805 【模板】manacher

给定一个串

s

，求最长回文子串的长度。

|s| \le 1.1 \times 10^7

。

模板题，根据以上讲解实现。

CPP

#include <bits/stdc++.h>
using namespace std;
int p[30000005], mx, id;
//注意：本题数据范围较大，要注意数组大小
//代码中 mx 即为讲解中的 r，id 为讲解中的 j'
int main() {
	string s = "##";
	char c; while(cin >> c) s += c, s += "#";
    //插入 #；为防止越界，在最前面也插一个 #
	int n = s.size(); s = ' ' + s;
	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]++; //暴力计算 p[i]
		if(i + p[i] > mx) mx = i + p[i], id = i; //更新右端点 r
	} int ans = 0; for(int i = 1;i <= n;i++) ans = max(ans, p[i]-1);
	cout << ans << endl;
	return 0;
}

P1659 [国家集训队] 拉拉队排练

在 Manacher 过程中，记录

cnt_i

表示回文半径为

i

的回文串个数，然后根据题目要求乘法原理即可。

时间复杂度

O(|s|+n\log K)

，可以通过。

CPP

#include <bits/stdc++.h>
using namespace std;
using ll = long long; const ll mod = 19930726;
int p[1000005]; ll cnt[1000005]; ll power(ll a, ll b) {
	ll ans = 1; while(b) {
		if(b & 1) ans = (ans * a) % mod; a = (a * a) % mod; b >>= 1;
	} return ans;
} int main() {
	int n; ll k; cin >> n >> k; int r = 0, mid = 0;
	string s; cin >> s; s = ' ' + s; for(int i = 1;i <= n;i++) {
		p[i] = (i > r ? 1 : min(p[mid*2-i], r-i+1));
		while(s[i+p[i]] == s[i-p[i]]) p[i]++; cnt[p[i]]++;
		if((i + p[i]) > r) { r = i + p[i] - 1; mid = i; }
	} ll ans = 1; for(int i = n;i >= 1;i--) {
		cnt[i] += cnt[i+1];
		if(cnt[i] <= k) k -= cnt[i], ans = (ans * power(2 * i - 1, cnt[i])) % mod;
		else { ans = (ans * power(2 * i - 1, k)) % mod; k = 0; break; }
	} cout << (k == 0 ? ans : -1) << endl;
	return 0;
}

\Large\textup{\bf{Part 5 : 尾声}}

Manacher 虽然应用场景不多，但是其思维值得我们学习。这种“利用前面已知信息加速后面计算”的思想，在 KMP 和 AC 自动机等算法中均有应用。

【7】Manacher 学习笔记

文章操作

相关推荐

评论

【7】Manacher 学习笔记