Luogu P4287 [SHOI2011]双倍回文

发表于 更新于 分类于 阅读次数： 本文字数： 628 阅读时长 ≈ 1 分钟

Link

Description

记字符串的倒置为 wRw^R。例如 (abcd)R=dcba(abcd)^R = dcba。

“双倍回文”为形如 wwRwwRww^Rww^R 的字符串。

给定一个字符串 ss，求 ss 的最长的双倍回文子串长度。

Solution

观察双倍回文的性质，发现双倍回文整体是一个回文串，它的一半也是一个回文串。考虑找到所有满足条件的双倍回文。

对于每个 xx，找到最远的 yy，其中 xx 为双倍回文字串的中点，yy 为右端点。

答案即为 max{(y−x)×2}max\{(y-x)\times 2\}

对于每对 (x,y)(x,y)，需要满足

fx≥2×(y−x)f_x \ge 2 \times (y-x)

fy≥y−xf_y \ge y-x

其中 fif_i 表示以 ii 为回文中心的最长回文串长度，用 manachermanacher 预处理即可。

整理上面的式子可得

y≤x+fx2y\le x + \dfrac{f_x}{2}

fy−y≥xf_y-y \ge x

所以我们把 fy−yf_y-y 排个序，这样枚举 xx 时，yy 只会变多，不会减少，开个 setset 维护一下，将当前满足条件1的 yy 加入 setset，再二分找答案。

注意双倍回文要保证 fxf_x 为偶数，并且 y−xy-x 也为偶数。

Code

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;

const int N = 2e6 + 5;
int n;
char s[N];
int f[N], ans;
struct node
{
    int val, id;
    friend bool operator < (node x, node y)
    {
        return x.val < y.val;
    }
}a[N];
set <int> S;

void read(char s[])
{
    s[0] = '@', s[1] = '#';
    n = 1;
    char c = getchar();
    while(c < 'a' || c > 'z') c = getchar();
    while(c >= 'a' && c <= 'z') s[++n] = c, s[++n] = '#', c = getchar();
    return;
}

void manacher()
{
    for(int i = 1, r = 0, mid = 0; i <= n; i++)
    {
        if(i <= r) f[i] = min(f[(mid << 1) - i], r - i + 1);
        while(s[i + f[i]] == s[i - f[i]]) f[i]++;
        if(i + f[i] > r) r = i + f[i] - 1, mid = i;
    }
    return;
}

void solve()
{
    for(int i = 1; i <= n; i++)
        f[i]--, a[i].val = i - f[i], a[i].id = i;
    sort(a + 1, a + 1 + n);
    for(int i = 1, j = 1; i <= n; i++)
    {
        while(j <= n && a[j].val <= i) S.insert(a[j].id), j++;
        if(f[i] & 1) continue;
        auto pos = --S.upper_bound(i + f[i] / 2);
        if((*pos - i) % 2 == 0) ans = max(ans, (*pos - i) << 1);
    }
    printf("%d\n", ans);
    return;
}

int main()
{
    scanf("%d", &n);
    read(s);
    manacher();
    solve();
    return 0;
}