如何正确使用马拉车 (manacher)

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

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

我们用 r[i] 表示每个点能扩展出的最长长度（就当它是半径吧），用 maxright 表示当前已经向右扩展的最大位置。
从第一个位置开始遍历。当 i 在 mid < 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;
}