Manacher算法：最长回文串（以每个点为中心的回文串长度）
直接上代码
MY_Code:
//22.10.8 Manacher顶级理解
#include<bits/stdc++.h>
using namespace std;
const int N=4e7;
int pos,maxr;//最右回文串的中心点、右端点
int p[N];//以i为中心的最长回文串长度
char str[N],s[N];
int main(){
cin>>(s+1);
int n=strlen(s+1);
//每个字符中间插入一个[奇怪的字符]，不用对偶数回文与奇数回文特殊判断
//另一方面暴力宽扩展的时候到达边界即可停止，因为边界符号最[奇怪]
for(int i=1;i<=n;i++){
str[i<<1]=s[i];
str[(i<<1)|1]='#';
}
str[0]='@';
str[1]='#';
n=(n<<1)|1;
for(int i=1;i<=n;i++){
//充分利用回文串的对称性以及回文串已处理长度
if(i<maxr){
//对于一个点 如果i<maxr，即可处理i关于pos对称点j已处理的回文串大小
//但是即便对称点回文长度再大，也不可能超过maxr
//同时在p[j]极长时即i+p[j]>maxr了，可使用的已处理回文串长度不会超过maxr-i，因为之后没有一个回文串扩展到，是未知的
p[i]=min(p[(pos<<1)-i],maxr-i);
}
while(str[i-p[i]-1]==str[i+p[i]+1]) p[i]++;//基操 暴力扩展
if(i+p[i]>maxr){//维护最右的回文串的pos与maxr
maxr=i+p[i];
pos=i;
}
}
int ans=1;
for(int i=1;i<=n;i++){
ans=max(ans,p[i]);
//左边扩展k个字符，相应的右边也是扩展k个字符，
//我们去除所有#号后得到的正好就是p[i]大小
}
printf("%d\n",ans);
return 0;
}