1 #include <iostream> 2 #include <string.h> 3 #include <algorithm> 4 #include <stdio.h> 5 #include <math.h> 6 using namespace std; 7  8 int Proc(char pszIn[],char pszOut[]) 9 {10     int nLen=1;11     pszOut[0]=‘$‘;12     int i=0;13     while(pszIn[i]!=‘\0‘)14     {15         pszOut[nLen++]=‘#‘;16         pszOut[nLen++]=pszIn[i];17         i++;18     }19     pszOut[nLen++]=‘#‘;20     pszOut[nLen]=0;21     return nLen;22 }23 void Manacher(int *p,char *str,int len)24 {25     int mx=0,id=0;26     for(int i=0;i<len;i++)27     {28         p[i]=mx>i?min(p[2*id-i],mx-i):1;29         while(str[i+p[i]]==str[i-p[i]])p[i]++;30         if(i+p[i]>mx)31         {32             mx=i+p[i];33             id=i;34         }35     }36 }37 const int MAXN=2200010;38 char strIn[MAXN];39 char strOut[MAXN];40 int p[MAXN];41 int main()42 {43     int t;44     scanf("%d",&t);45     while(t--)46     {47         scanf("%s",strIn);48         int nLen=Proc(strIn,strOut);49         Manacher(p,strOut,nLen);50         int ans=1;51         for(int i=0;i<nLen;i++)52             ans=max(ans,p[i]);53         printf("%d\n",ans-1);54     }55     return 0;56 }