回文子串的最大长度（字符串哈希+二分）

139. 回文子串的最大长度 - AcWing题库高质量的算法题库https://www.acwing.com/problem/content/description/141/正序倒序求两次哈希，然后再通过枚举中点来求最长的回文子串（分偶和奇回文）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define lowbit(x) ((x)&(-x))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using pll=pair<ll,ll>;
const int MAXN=1e6+5;
const int INF=0x3f3f3f3f;
const ll NNF=0x3f3f3f3f3f3f3f3f;



char s[MAXN];
ull h1[MAXN];
ull h2[MAXN];
ull k[MAXN];
const int p=131;

ull get1(int l,int r){
	return h1[r]-h1[l-1]*k[r-l+1];
}
ull get2(int l,int r){
	return h2[l]-h2[r+1]*k[r-l+1];
}


int main(){
	int t=0;
	while(scanf("%s",s+1)&&strcmp(s+1,"END")){
		int n=strlen(s+1);
		k[0]=1;
		h2[n+1]=0;
		for(int i=1;i<=n;i++){
			h1[i]=h1[i-1]*p+(ull)s[i];
			k[i]=k[i-1]*p;
		}
		for(int i=n;i>=1;i--){
			h2[i]=h2[i+1]*p+(ull)s[i];
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			int l=0,r=min(i-1,n-i);
			while(l<=r){
				int mid=l+r>>1;
				if(get1(i-mid,i-1)==get2(i+1,i+mid)) l=mid+1;
				else r=mid-1;
			}
			ans=max(ans,r<<1|1);
			l=0,r=min(i,n-i);
			while(l<=r){
				int mid=l+r>>1;
				if(get1(i-mid+1,i)==get2(i+1,i+mid)) l=mid+1;
				else r=mid-1;
			}
			ans=max(ans,r<<1);
		}
		printf("Case %d: %d\n",++t,ans);
	}
	return 0;
}