acwing139. 回文子串的最大长度

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const int N = 2000000 + 10 , P = 131 ;
typedef unsigned long long ULL ;
ULL hl[N] , hr[N] ,p[N];
char a[N] ;
ULL get(ULL h[] ,ULL l ,ULL r){
  return h[r] - h[l-1] * p[r - l + 1] ;
}
int main(){
  int cnt = 1 ;
  while(1){
    
    scanf("%s",a+1) ;
    if(a[1]=='E') break ;
    int n = strlen(a+1) ;
    for(int i = n*2 ; i  ; i -= 2 ){
      a[i] = a[i/2] ;
      a[i-1] = 'a' + 26 ;
    }
    n *= 2 ;
    p[0] = 1 ;
    for(int i = 1 , j = n; i <= n ; i ++ , j -- ){
      hl[i] = hl[i-1] * P + a[i] - 'a' + 1  ;
      hr[i] = hr[i-1] * P + a[j] - 'a' + 1 ;
      p[i] =  p[i-1] *P ;
    }
    int res = 0 ;
    for(int i = 1 ; i <= n ;i  ++){
      int l = 0 , r = min(i-1 , n-i) ;
      while(l < r){
        int mid = r + l + 1 >> 1 ;
        if(get(hl,i-mid,i-1) == get(hr,n - (i + mid) + 1,n - (i+1)+1)) l = mid ;
        else r = mid - 1 ;  
      }
      if(a[i-l] <= 'z') res = max(res,l+1) ;
      else res = max(res,l) ;
    }
    printf("Case %d: %d\n", cnt ++ , res);
  }
  return 0 ;
}