模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| char s[maxn << 1] = "##";
int n, hw[maxn << 1];
int l[maxn << 1], r[maxn << 1];
void manacher(char* a) {
int len = strlen(a);
for (int i = 0; i < len; i++) {
s[i * 2 + 2] = a[i];
s[i * 2 + 3] = '#';
}
n = len * 2 + 2;
s[n] = 0;
int maxr = 0, m = 0;
for (int i = 1; i < n; i++) {
if (i < maxr)
hw[i] = min(hw[m * 2 - i], hw[m] + m - i);
else
hw[i] = 1;
while (s[i + hw[i]] == s[i - hw[i]]) hw[i]++;
if (hw[i] + i > maxr) {
m = i;
maxr = hw[i] + i;
}
}
}
|
例题
最长双回文串
https://www.luogu.com.cn/problem/P4555
题意
在给定的字符串中找到两个相邻的回文串,长度最长
思路
将Manacher处理后的"#"当作两个回文串的连接点
注意这个处理步骤:
1
2
| l[i + hw[i] - 1] = max(l[i + hw[i] - 1], hw[i] - 1);
r[i - hw[i] + 1] = max(r[i - hw[i] + 1], hw[i] - 1);
|
还有这个步骤:
1
2
3
4
| for (int i = 3; i <= n;i+=2)
r[i] = max(r[i], r[i - 2] - 2);
for (int i = n; i >= 1;i-=2)
l[i] = max(l[i], l[i + 2] - 2);
|
代码 : https://xlorpaste.cn/jtcnhg