以为例。

manacher算法：

设一个数组p，p[i]表示以第i个字符为中心的最大半径，最大的p[i]就是最长的回文子串了。

不过这样要用两个循环，时间复杂度是(n*n)。

1 int solve(){ 2     int len = strlen(str), ans = 0; 3     for(int i = 0; i < len; i ++){ 4         for(int j = 0; i-j>=0 && i+j < len; j++){ 5             if(str[i-j] != str[i+j])break; 6             if(j*2+1 > ans) ans=j*2+1; 7         } 8         for(int j = 0; i-j >= 0 && i+j+1 < len; j ++){ 9             if(str[i-j] != str[i+j+1])break;10             if(2*j+2 > ans) ans = 2*j+2;11         }12     }13     return ans;14 }

而manacher算法可以快速的求p[i],设i之前的最大值为p[id]+id，那么p[id]+id大于i时，p[i] = min(p[2*id-i],p[id]+id-i)，否则p[i] = 1，具体的证明过程可以参考。

AC代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int MAX = 1e6+10; 6 char str[MAX<<1]; 7 int p[MAX<<1]; 8 int solve(){ 9     int ans = 0, id = 0, len = strlen(str);10     for(int i = len; i >= 0; i --){11         str[i+i+2] = str[i];12         str[i+i+1] = '#';13     }14     str[0] = '*';15     for(int i = 2; i<2*len+1; i ++){16         if(p[id] + id > i) p[i] = min(p[2*id-i],p[id]+id-i);17         else p[i] = 1;18         while(str[i-p[i]] == str[i+p[i]])++p[i];19         if(p[id] + id < p[i]+i) id = i;20         if(ans < p[i]) ans = p[i];21     }22     return ans-1;23 }24 int main(){25     int n;26     scanf("%d",&n);27     while(n--){28         scanf("%s",str);29         printf("%d\n",solve());30         memset(str,0,sizeof(str));31         memset(p,0,sizeof(p));32     }33     return 0;34 }