https://www.cnblogs.com/grandyang/p/4475985.html
思路是学习的是上面博客的想法，思路很清晰 优化的方法和exkmp有异曲同工的地方
博客里的内容我在这里就不重复累赘的叙述了，浪费时间
我们需要只要关键数组p[]表示位置为i的字符串的半径，并且我们需要记住以下几个性质
1.最长子串的长度为最长半径减1(用来求长度)
2.起始位置是中间位置减去半径再除以2（用来求字符串）
int p[]; //记录半径
void manacher(string s){
string ma="";
ma+='$';
ma+='#';
int len=s.length();
//预处理字符串 加#是为了让长度变为奇数(避免讨论奇偶)
//二加$则是为了求字符串的起始位置 在博客中有相关叙述
for(int i=;i<len;i++){
ma+=s[i];
ma+='#';
}
int po=; int mx=; //po记录当前可以延伸到最右端的点 mx为长度
len=ma.length();
for(int i=;i<len;i++){
p[i]=mx>i?min(p[*po-i],mx-i):; //关键代码 在博客中理解
while(ma[i+p[i]]==ma[i-p[i]]) p[i]++;
if(i+p[i]>mx){ //更新
mx=i+p[i];
po=i;
}
}
}