————引用博客
跟kmp基本流程相似，求解过程中需要对分析串进行预处理，求解p[i]使其能表示匹配串中回文串的关系
int manacher(string s) { string t="*#"; for(int i=0;i<s.size();i++){ t+=s[i]; t+="#"; } vector<int > p(t.size(),0); int mx=0,id=0,str_center=0,str_len=0; for(int i=1;i<s.size();++i){ p[i]=mx>i?min(p[2*id-i],mx-i):1; while(t[i+p[i]]==t[i-p[i]]) ++p[i]; if(mx<p[i]+i){ mx=p[i]+i; id=i; } if(str_len<p[i]-1){ str_len=p[i]-1; str_center=i; } } return str_len-1; }跟kmp不同的是在进行求解p[i]之前需要对匹配串进行预处理 ，使其扩展为奇数为串避免分支讨论 在此基础上分析出最长回文半径和最长回文子串长度之间的关系：
int maxLength = p[i]-1其中maxLength表示最长回文子串长度 为方便分析合并杂余讨论项将串下标整体后移一位 最长回文子串的起始索
int index = (i - p[i])/2