Manacher 学习笔记

模板及讲解

Manacher是什么

Manacher 算法是用于算一个字符串最长回文子串长度的一个算法,其时间复杂度为$O(n)$

Manacher的实现

例题:Luogu: (模板)manacher算法

给出一个只由小写英文字符组成的字符串S, 字符串长度为n,求S中最长回文串的长度

暴力

1、直接枚举区间判回文串,$O(n^3)$

2、由于回文串关于中间点/中间点的线,枚举对称轴向两边扩展分奇偶讨论即可,$O(n^2)$

Manacher

因为字符串有奇有偶,所以我们要进行操作免除奇偶性讨论,我们在0处加一个’\$’, 最后面加’\0’,中间每个字符之间加’#’,即可将除了头尾两个字符以外的字符串长度都变成奇数个。例如abca可以变为\$#a#b#c#a#\0’,则变为奇数个,对称中心为中间那个字符。
我们设$p_i$为以$i$为对称中心,最长的回文半径长度。#a#b#b#b#a#中间的字符的$p_i$值为6,则$p_i-1$的值是以$i$为对称中心的最长回文子串长度。设$mr$为回文串最右能触及到的地方,$pos$为这个回文串的对称中心位置。

步骤:1、给$p_i$赋初值 2、向两边扩展 3、更新$mr$和$pos$

给$p_i$赋初值, 下面分两种情况讨论;
1、$i$在$mr$左边

$j=2 \cdot pos - i $为$i$关于$pos$的对称点。

当$j$的回文子串很小不超过左半区间时,我们令$p_i=p_j$,如下图(根据对称性,$i$的回文子串一定包含$j$的回文子串)
Markdown

当$j$的回文子串很大超过左半区间时,我们只能确定$p_i=mr-i$
Markdown

2、$i$在$mr$右边
此时$i$没有对称的$j$给它赋值,只能$p_i=1$

然后扩展字符串,之后不要忘记更新$mr, pos$的值,因为我们要使得$mr$更大,才能更多调用$p_i=p_j$

代码

例题:Luogu: (模板)manacher算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 11000000 + 5;
char s_old[MAXN], s[MAXN * 2];//旧数组,新数组
int n, cnt, pos, mr, p[MAXN * 2];//n,新数组长度cnt,pos,mr,以i为对称轴最长回文半径长度p
int manacher() {
int ret = 0;
for (int i = 1; i <= cnt; i++) {
if (i < mr) p[i] = min(p[2 * pos - i], mr - i); else p[i] = 1;//对称性继承
while (s[i + p[i]] == s[i - p[i]]) p[i]++;//向两边扩展 ,不用判边界因为 前有$后有\0
if (i + p[i] - 1 > mr) mr = i + p[i] - 1, pos = i;//更新mr,注意用 i + p[i] - 1更新
ret = max(ret, p[i] - 1);//更新答案
}
return ret;
}
void clean() {
mr = -1, cnt = 1;
}
int solve() {
clean();
n = strlen(s_old), s[0] = '$', s[1] = '#';
for (int i = 0; i < n; i++) s[++cnt] = s_old[i], s[++cnt] = '#';
s[cnt + 1] = '\0';//处理字符串,前加$后加\0
printf("%d\n", manacher());
return 0;
}
int main() {
scanf("%s", s_old), solve();
return 0;
}

常见题型

1、求最长回文子串
Q:给出一个只由小写英文字符组成的字符串S, 字符串长度为n,求S中最长回文串的长度
解:见解析
例题:Luogu: (模板)manacher算法

------ 本文结束 ------