manacher 算法是用来求最长回文串长度的算法,复杂度是线性的($O(n)$)
基本思想是枚举以每一个点为中心,找出可以扩展的最长长度(用 r[i] 表示),然而会出现长度为偶数的情况无法枚举到的情况,所以首先要把字符串预处理一下。

如何预处理?只要把字符串之间的空隙用一个特殊字符(比如 '#')填满就好了(因为奇数加偶数还是一个奇数),把第 0 位设为 '#',在下面的代码中,预处理后的字符串是 expa
然而仅仅这样做是不够的,会有很多重复的访问,复杂度大幅上升。

我们用 r[i] 表示每个点能扩展出的最长长度(就当它是半径吧),用 maxright 表示当前已经向右扩展的最大位置。
从第一个位置开始遍历。当 imid < i < maxright 时,r[i] = min(r[mid * 2 - i], maxright - i)
如果发现关于 mid 对称的两点 expa[i + r[i]]expa[i - r[i]] 的字符相同,就继续更新 r[i]
如果 i 跑到了 midright 的右边,我们只能设 r[i] = 1

#include <bits/stdc++.h>
using namespace std;
const int maxN = 11000000 + 5;
char str[maxN], expa[maxN << 1];
int r[maxN << 1];
int ans, len;
void init() { // 预处理
    len = strlen(str);
    expa[0] = expa[1] = '#';
    for (int i = 0; i < len; i++) {
        expa[i * 2 + 2] = str[i];
        expa[i * 2 + 3] = '#';
    }
    len = len * 2 + 2;
    expa[len] = 0;
}
int manacher() {
    int maxright = 0, mid = 0;
    for (int i = 1; i < len; i++) {
        if (i < maxright) // 如果 i 在 maxright 左边
            r[i] = min(r[(mid << 1) - i], r[mid] + mid - i);
            // r[i] = min(r[mid * 2 - i], maxright - i)
        else r[i] = 1;
        while (expa[i + r[i]] == expa[i -r[i]]) r[i]++;
        // 这里的 i 相当于 mid,如果能继续扩展则扩展
        if (r[i] + i > maxright) {
            maxright = r[i] + i;
            // maxright = max(maxright, r[i] + i),更新能够向右扩展的最大位置
            mid = i; // 更新 mid
        }
    }
    int tmp = 1;
    for (int i = 0; i < len; i++)
        tmp = max(tmp, r[i]); // 找出 r 数组中的最大值
    return --tmp; // 不需要除以 2,因为我们求的是半径
}
int main() {
    scanf("%s", str);
    init();
    cout << manacher() << endl;
    return 0;
}