Manacher算法是一种优化的暴力算法，其精髓在于利用了回文串的基本性质——左右对称性。
最简单的情况就是以每个点为中心（先将两个字符之间的空隙也视为字符），从中心开始往左右扩散直至左右不相等则结束，但是如果从左到右地求解，由于回文串的基本性质，如果恰好当前要求解的位置i在某个回文串s中，那么此时（后面还可能会更新）i的回文信息可以用i关于s的对称点j处的信息来初始化，因为j处的信息在i一定成立。
观察上述流程，显然可以加入三个辅助的变量（数组）
- 需要一个数组
p[M]来记录每个点的回文信息，最简单的就记录每个点能扩展的右边界（开区间）
- 一个变量
maxr记录当前位置是否在之前某个求解过的回文子串内部，即维护最长的回文子串右边界（开区间）
- 为了方便获得当前点的对称点，用
mid记录maxr对应的最长回文子串的中心点位置
然后为了统一奇偶回文的中心点是否存在问题，将原始串用#和$做间隔处理，然后用处理后的串做Manacher算法扫描，处理后的串长这样：
P3805 【模板】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
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
const int N = 11000005;
int p[N << 1];
char str[N <<1];
char s[N];
int main(void)
{
scanf("%s", s);
int n = strlen(s);
int sz = 0;
str[sz++] = '$';
str[sz++] = '#';
for (int i = 0; i < n; ++i)
{
str[sz++] = s[i];
str[sz++] = '#';
}
str[sz] = 0;
int mr = 0, mid = 0;
for (int i = 1; i < sz; ++i)
{
if(i < mr)
{
p[i] = min(p[2 * mid - i], mr - i);
}
else
p[i] = 1;
while (str[i - p[i]] == str[i + p[i]])
++p[i];
if(i + p[i] > mr)
{
mr = i + p[i];
mid = i;
}
}
int ans = 0;
for (int i = 2; i < sz - 1; ++i)
{
ans = max(ans, p[i] - 1);
}
printf("%d\n", ans);
return 0;
}
|