个人感觉马拉车算法的思想和扩展KMP的思想是相似的。
首先对于这个问题，我们可以暴力枚举每个子串，然后判断是否是回文串，时间复杂度大概是O(n^3)，我们运用下尺取法的思想，枚举每一个对称轴位置(针对长度的奇偶有所区别)，那么时间复杂度会是O(n^2)，接着我们如果把字符串转化一下，添加一些未出现过的字符，形成一个长度为奇数的字符串。那么我们只用枚举每一个长度然后判断就好了。所以如何利用已经得到的信息判断最长就是一个优化点。
我们用pos，maxright记录最大回文半径，以pos为对称轴，maxright为最大右边的位置，len[i]表示以i为对称轴的回文半径长
对于当前的i,可能有两种情况：（首先一定在pos的右边）
1 i在maxright左边
此时i关于pos的对称位置为j, 那么此时关于i为对称轴，已经形成回文串的位置有min(len[j],maxright-i)
2 i在maxright的右边
此时就需要从头开始进行匹配。
int init(char *s)//将原字符串转化为带有特殊标志的字符串t { int len=strlen(s); t[0]='@';//防止越界 for(int i=1;i<=2*len;i+=2) { t[i]='#'; t[i+1]=s[i/2]; } t[len*2+1]='#'; t[len*2+2]='$';//防止越界 return 2*len+1; } int MANACHER(char *s,int lens)//按照马拉车算法的思想进行操作 { int mx=0,ans=0,pos=0; for(int i=1;i<=lens;i++) { if(mx>i) len[i]=min(len[2*pos-i],mx-i); else len[i]=1; while(s[i-len[i]]==s[i+len[i]]) len[i]++; if(len[i]+i>mx) { mx=len[i]+i; pos=i; } ans=max(ans,len[i]); } return ans-1; }
