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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 1e7 + 1e6;

char str[MAXn * 2 + 10];
int rad[MAXn * 2 + 10];
void EvaRad(int len) {
    for (int i = 1, l = 1, r = 0; i <= len; ++i) {
        if (i > r) rad[i] = 0;
        else rad[i] = min(r - i, rad[r + l - i]);
        while (i + rad[i] < len && i - rad[i] > 1 && str[i + rad[i] + 1] == str[i - rad[i] - 1]) ++rad[i];
        if (i + rad[i] > r) {
            r = i + rad[i];
            l = i - rad[i];
        }
    }
}

char strfirst[MAXn + 10];
int len1, len2, ans;
signed main() {
    scanf("%s", (strfirst + 1));
    len1 = strlen(strfirst + 1);
    str[++len2] = '#';
    for (int i = 1; i <= len1; ++i) {
        str[++len2] = strfirst[i];
        str[++len2] = '#';
    }
    EvaRad(len2);
    for (int i = 1; i <= len2; ++i) {
        ans = max(ans, i & 1 ? (rad[i] & (~1)) : (rad[i] & (~1)) + 1);
    }
    printf("%d\n", ans);
    return 0;
}