https://www.luogu.com.cn/problem/P3805
1. 为了统一处理奇偶数两种情况，在每个字符间隙加上其他字符如：’#’，同时还要在边界 s[0], s[len + 1] 加上不相同的字符，如 abab，@#a#b#a#b#$。
2. 定义数组 p[i] 为第 i 个位置能扩展的长度，如：1，2，1，1，1，2，1，1，1。
3. 在第一点的基础上，那么正确答案就是 max(p[i] - 1)。
4. 定义 c 为 i 前面能扩展最远的下标，定义r 为 c + p[i]。
5. 当 i < r 时，那么 p[i] = min(r - i, p[2 * c - i])。
6. 否则 p[i] = 1，进行暴力求解。
7. 最后一步，更新 c 和 r。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e7 + 10;

char str[N], s[N * 2];
int p[N * 2];

void init() {
    int len = strlen(str + 1);
    s[0] = '@';
    for(int i = 1; i <= len; i++) {
        s[i * 2 - 1] = '#';
        s[i * 2] = str[i];
    }
    s[len * 2 + 1] = '#';
    s[len * 2 + 2] = '#';
}

int manacher() {
    int c = 0, r = 0, ans = 0;
    for(int i = 1; s[i]; i++) {
        if(i < r) p[i] = min(r - i, p[2 * c - i]);
        else p[i] = 1;
        while(s[i + p[i]] == s[i - p[i]]) p[i]++;
        if(i + p[i] > r) {
            r = i + p[i];
            c = i;
        }
        ans = max(ans, p[i]);
    }
    return ans - 1;
}

int main() {
    scanf("%s", str + 1);
    init();
    cout << manacher() << endl;
    return 0;
}