什么是 Manacher
Manacher 算法可以以 \(O(|S|)\) 的时间复杂度求出一个字符串的最长回文子串。
算法过程
令 \(k_i\) 为以 \(i\) 为回文中心向右扩展到的最远的位置（即若串 \(T_{l\sim r}\) 回文串，那么 \(T\) 的回文中心为 \(T_{\frac{l+r}{2}}\)），注意到偶数长度的串不具有回文中心，所以我们需要手动添加一些不在字符集里的特殊字符来人为制造回文中心。
具体的，对于一个字符串 \(S_{1\sim n}\)，将每对相邻字符间和字符串两侧放入不在字符集里的相同字符（如#），将 \(S_{1\sim n}\to S'_{1\sim 2n-1}\)，然后给字符串的开头或者末尾中的一处添加另一种特殊字符，如@。
例子：\(S=\)cjwenandmasterhuangakioi，\(S'=\)@#c#j#w#e#n#a#n#d#m#a#s#t#e#r#h#u#a#n#g#a#k#i#o#i#。
那么若已经求出 \(k_{1\sim i-1}\)，如何求出 \(k_i\) 呢？
注意到回文串有一个很好性质，那就是回文（
所以说，有 \(\forall j, k_j\ge i,j<i\)，\(k_i\ge \min(i+k_{2j-i}-(2j-i),k_j)\)
画个图理解一下：
若以 \(2j-i\) 为回文中心的回文串并没有超过 \(j\) 为回文中心的回文串，那么啥事没有，\(k_i=i+k_{2j-i}-(2j-i)\) 即可。
若以 \(2j-i\) 为回文中心的回文串超过了 \(j\) 为回文中心的回文串，那么超过部分并不能算作 \(k_i\) 的答案，因为 \(S_{k_j+1} \neq S_{2k_j-j-1}\)，所以答案应当回缩为 \(2k_j-j\)，对称一下就是 \(k_j\) 了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1.1e7 + 5;
char s0[N], s[N << 1];
int n0, n, r, m, ans, k[N << 1];
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> s0 + 1;
n0 = strlen(s0 + 1);
s[0] = '_';
for(int i = 1; i <= n0; i ++)
s[(i << 1) - 1] = '#', s[i << 1] = s0[i];
s[n0 << 1 | 1] = '#';
n = strlen(s + 1);
for(int i = 1; i <= n; i ++)
{
if(i <= r) k[i] = min(r, i + k[(m << 1) - i] - (m << 1) + i);
else k[i] = i;
while(s[k[i] + 1] == s[(i << 1) - k[i] - 1]) k[i] ++;
if(k[i] >= r) r = k[i], m = i;
ans = ans < k[i] - i ? k[i] - i : ans;
}
cout << ans;
return 0;
}