题目：

本来是想练习一下字符串哈希算法的，没想到改了好久的二分，23333。

求字符串中的最长回文字串以前我一直用的dp，当然这道题用dp会T。用哈希+二分可以达到O(NlogN)的时间复杂度。

首先进行正反两次字符串哈希。

然后分长度为奇数或偶数两种情况，对于每一个位置i，二分它向一个方向可以延伸的长度，判断使用之前预处理的字符串哈希。

当然二分要注意方法，不然可能会wa掉。

这道题要求取满足条件的最大值，应该这样二分：

int Division(){    int l=ledge,r=redge;    while(l
     
      >1;        if(judge(mid)) l=mid;        else r=mid-1;    }    return l;}
     

而很多题可能求满足条件的最小值，这样二分：

int Division(){    int l=ledge,r=redge;    while(l
      
       >1;        if(judge(mid)) l=mid+1;        else r=mid;    }    return l;}
      

附上ac代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef unsigned long long ULL;char s1[1000010],s2[1000010];ULL f1[1000010],f2[1000010],p[1000010];int len=0;int OddDivision(int i){    int l=0,r=min(i-1,len-i);    while(l
         
          >1;        if(f1[i-1]-f1[i-mid-1]*p[mid]==f2[len-i]-f2[len-i-mid]*p[mid])            l=mid;        else r=mid-1;    }    return l;}int EveDivision(int i){    int l=0,r=min(i-1,len-i+1);    while(l
          
           >1; if(f1[i-1]-f1[i-mid-1]*p[mid]==f2[len-i+1]-f2[len-i+1-mid]*p[mid]) l=mid; else r=mid-1; } return l;}int main(){ int Case=0; while(~scanf("%s",s1+1)) { Case++; if(!strcmp(s1+1,"END")) break; len=strlen(s1+1); for(int i=len;i>=1;i--) s2[len-i+1]=s1[i];s2[len+1]='\0'; p[0]=1; for(int i=1;i<=len;i++) { f1[i]=f1[i-1]*131+s1[i]-'a'+1; f2[i]=f2[i-1]*131+s2[i]-'a'+1; p[i]=p[i-1]*131; } int ans=0; for(int i=1;i<=len;i++) { int odd=OddDivision(i); ans=max(ans,odd*2+1); int eve=EveDivision(i); ans=max(ans,eve*2); } printf("Case %d: %d\n",Case,ans); } return 0;}