这题可用拓展KMP分治法来做复杂度O(nlogn)这种方法好复杂而且代码很长，不易理解。
相比之下Manacher就简单多了，算法本身也很简单 这里个易懂的资料
复杂度O(n)
kuangbin的模版（有一处修改）
/* * 求最长回文子串 */const int MAXN=110010;char Ma[MAXN*2];int Mp[MAXN*2];void Manacher(char s[],int len){int l=0;Ma[l++]='$';Ma[l++]='#';for(int i=0;i<len;i++){Ma[l++] = s[i];Ma[l++] = '#';}Ma[l]=0;int mx=0,id=0;//mx记录在求i之前的回文串中,延伸至最右端的位置的下一格.for(int i=1;i<l;i++){//i=0的位置永远用不到，因为不可能有mx之内的点关于id的对称点是i=0,所以i从1开始，//从0开始的时候会导致后面i-Mp[i]=-1，binshen的模板在这有点小问题Mp[i] = mx>i? min(Mp[2*id-i],mx-i):1;while(Ma[i+Mp[i] ]==Ma[i-Mp[i] ]) Mp[i]++;if(i+Mp[i]>mx){mx=i+Mp[i];id=i;}}}显然这种算法的复杂度是O(n)的，，mx范围内的i可以在O(1)时间内解决或者边拓展mx边解决，所以mx最大只能拓展O(n)，所以总复杂是O(n)的。
//249MS 2184K#include<cstdio>#include<iostream>#include<cstring>#define M 111111using namespace std;char s[M];char Ma[M<<1];int Mp[M<<1],ans;void Manacher(char s[],int len){int l=0;Ma[l++]='$';Ma[l++]='#';for(int i=0;i<len;i++){Ma[l++] = s[i];Ma[l++] = '#';}Ma[l]=0;int mx=0,id=0;for(int i=1;i<l;i++){//i=0的位置永远用不到，因为不可能有mx之内的点关于id的对称点是i=0,所以i从1开始，//从0开始的时候会导致后面i-Mp[i]=-1，binshen的模板在这有点小问题Mp[i] = mx>i? min(Mp[2*id-i],mx-i):1;while(Ma[i+Mp[i] ]==Ma[i-Mp[i] ]) Mp[i]++;if(i+Mp[i]>mx){mx=i+Mp[i];id=i;}if(Mp[i]>ans) ans=Mp[i];}}int main(){while(~scanf("%s",s)){ans=-(1<<30);int len=strlen(s);Manacher(s,len);printf("%d\n",ans-1);}return 0;}
劝君更尽一杯酒，西出阳关无故人。
