Manacher | Moonglade

P3805 【模板】manacher 算法

#include <bits/stdc++.h>

using namespace std;

const int N = 2.2e7 + 7;

int n, ans, mid, mr, f[N];

char s[N], c;

int main() {
    s[++n] = '~';
    while(scanf("%c", &c) != -1) {
        s[++n] = '#';
        s[++n] = c;
    }
    s[++n] = '#';
    // printf("%s", s + 1);
    mid = mr = 1;
    for (int i = 2; i <= n; i++) {
        if (i < mr) {
            f[i] = min(f[(mid << 1) - i], mr - i + 1);
        } else {
            f[i] = 1;
        }
        while(s[i + f[i]] == s[i - f[i]]) {
            f[i]++;
        }
        if (i + f[i] - 1 > mr) {
            mr = i + f[i] - 1;
            mid = i;
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) ans = max(ans, f[i] - 1);
    printf("%d\n", ans);
    return 0;
}