DDOSvoid's Blog

Luogu P4555 [国家集训队]最长双回文串

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4555

Solution

我们用 $manacher$ 求出一个每个点为回文中心的最长回文子串的长度

然后用这个东西求 $l[i]$ 和 $r[i]$ 表示以 $i$ 结尾和以 $i$ 开始的最长回文子串的长度

具体有两种做法，一种是直接映射到原数组，另一种是映射到 # 上

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
47
48
49
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100010
using namespace std;

int n;

char c[maxn]; 

int N, mr, p, f[maxn * 2], Len; 
char s[maxn * 2]; 
void init(char *c) {
    int l = strlen(c + 1); s[0] = '~'; 
    for (int i = 1; i <= l; ++i)
        s[i * 2] = c[i], s[i * 2 - 1] = '#';
    N = 2 * l + 1; s[N] = '#';
}

void manacher() {
    for (int i = 1; i <= N; ++i) {
        if (i < mr) f[i] = min(f[2 * p - i], mr - i);
        while (s[i + f[i]] == s[i - f[i]]) ++f[i]; --f[i];
        if (f[i] + i > mr) mr = i + f[i], p = i;
        Len = max(Len, f[i]); 
    }
}

int l[maxn], r[maxn];

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> c + 1; n = strlen(c + 1); init(c); manacher();
    for (int i = 1; i <= N; ++i) {
        int L = i - f[i] + 1 >> 1, R = i + f[i] - 1 >> 1;
        if (!f[i]) continue; 
        l[L] = max(l[L], f[i]);
        r[R] = max(r[R], f[i]);
    } 
    for (int i = 1; i <= n; ++i) l[i] = max(l[i], l[i - 1] - 2);
    for (int i = n - 1; i; --i) r[i] = max(r[i], r[i + 1] - 2);
    for (int i = 1; i < n; ++i) ans = max(ans, r[i] + l[i + 1]);
    cout << ans << "\n";
    return 0;
} 

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
47
48
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100010
using namespace std;

int n;

char c[maxn]; 

int N, mr, p, f[maxn * 2], Len; 
char s[maxn * 2]; 
void init(char *c) {
    int l = strlen(c + 1); s[0] = '~'; 
    for (int i = 1; i <= l; ++i)
        s[i * 2] = c[i], s[i * 2 - 1] = '#';
    N = 2 * l + 1; s[N] = '#';
}

void manacher() {
    for (int i = 1; i <= N; ++i) {
        if (i < mr) f[i] = min(f[2 * p - i], mr - i);
        while (s[i + f[i]] == s[i - f[i]]) ++f[i]; --f[i];
        if (f[i] + i > mr) mr = i + f[i], p = i;
        Len = max(Len, f[i]); 
    }
}

int l[maxn * 2], r[maxn * 2];

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> c + 1; n = strlen(c + 1); init(c); manacher();
    for (int i = 1; i <= N; ++i) {
        l[i - f[i]] = max(l[i - f[i]], f[i]);
        r[i + f[i]] = max(r[i + f[i]], f[i]);
    } 
    for (int i = 3; i <= N; i += 2) l[i] = max(l[i], l[i - 2] - 2);
    for (int i = N - 2; ~i; i -= 2) r[i] = max(r[i], r[i + 2] - 2);
    for (int i = 1; i <= N; i += 2)
        if (l[i] && r[i]) ans = max(ans, r[i] + l[i]);
    cout << ans << "\n";
    return 0;
}