manacher 算法是用来求最长回文串长度的算法，复杂度是线性的（）
基本思想是枚举以每一个点为中心，找出可以扩展的最长长度（用 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
cpp
#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;
}