1 const int LEN=110005; 2 const int N=LEN*2; 3 int p[N]; 4 char str[LEN], tmp[N]; 5 //p[i]表示以str[i]为中心的回文往右延伸的 最长长度 6 void manacher(char* str, int* p){ 7 int n=strlen(str), i, id, mx; 8 for(p[mx=id=0]=i=1; i<n; i++){ 9 p[i]=mx>i?min(p[2*id-i], mx-i+1):1;10 while(i+p[i]<n&&i-p[i]>=0&&str[i+p[i]]==str[i-p[i]]) p[i]++;11 if(mx<i+p[i]-1){12 id=i;13 mx=i+p[i]-1;14 }15 }16 }17 //求str的最长回文的长度18 int maxPalindrome(char* str){19 int ans=0;20 int i, n;21 for(i=0, n=strlen(str); i<n; i++){22 tmp[2*i]=‘#‘;23 tmp[2*i+1]=str[i];24 }25 tmp[2*i]=‘#‘;26 tmp[2*i+1]=‘\0‘;27 n=n*2+1;28 manacher(tmp, p);29 for(i=0; i<n; i++){30 if(ans < p[i]-1){31 ans = p[i]-1;32 }33 }34 return ans;35 }