https://www.luogu.org/blog/codesonic/manacheralgorithm
先放上洛谷的链接，毕竟讲的真好
两道例题
luogu4555 SP7586
inline void change() {
s[]=s[]='#';
for(int i=; i<n; i++) {
s[i*+]=a[i];
s[i*+]='#';
}
n=n*+;
s[n]=;
}
//替换新串
inline void manacher() {
int maxright=,mid;
for(int i=; i<n; i++) {
if(i<maxright)
hw[i]=min(hw[(mid<<)-i],hw[mid]+mid-i);
else
hw[i]=;
while(s[i+hw[i]]==s[i-hw[i]])
++hw[i];
if(hw[i]+i>maxright) {
maxright=hw[i]+i;
mid=i;
}
}
}//主函数更新答案
马拉车算法