题目

代码

#include<bits/stdc++.h>
using namespace std;
string s,rs; 
long long bs=131,md=9999997,f[1000001],rf[1000001],p[1000001],lth,ans,l,r,mid,cs;
inline long long gnm(int l,int r){
	if(l>r) swap(l,r);
	if(l==0) return f[r];
	return (f[r]-f[l-1]*p[r-l+1]%md+md)%md;
}
inline long long rgnm(int l,int r){
	if(l>r) swap(l,r);
	if(l==0) return rf[r];
	return (rf[r]-rf[l-1]*p[r-l+1]%md+md)%md;
}
inline bool Jok(long long ps,long long qlth){
	return gnm(ps-qlth,ps+qlth)==rgnm(lth-1-ps+qlth,lth-ps-qlth-1);
}
inline bool Eok(long long ps,long long qlth){
	return gnm(ps-qlth+1,ps+qlth)==rgnm(lth-2-ps+qlth,lth-1-ps-qlth);
}
int main(){
	p[0]=1;
	while(cin>>s){
		if(s=="END") break;
		lth=s.size(),ans=0,rs="";
		for(int i=1;i<=lth;++i) p[i]=p[i-1]*bs%md;
		f[0]=s[0]-'a'+1;
		for(int i=1;i<lth;++i) f[i]=(f[i-1]*bs%md+s[i]-'a'+1)%md;
		for(int i=0;i<lth;++i) rs+=s[lth-i-1];
		rf[0]=rs[0]-'a'+1;
		for(int i=1;i<lth;++i) rf[i]=(rf[i-1]*bs%md+rs[i]-'a'+1)%md;
		for(long long i=0;i<lth;++i){
			l=0,r=min(i,lth-i-1);
			while(l<=r){
				mid=(l+r)/2;
				if(Jok(i,mid)) l=mid+1,ans=max(ans,2*mid+1);
				else r=mid-1;
			}
		}
		for(long long i=0;i<lth-1;++i){
			l=0,r=min(i+1,lth-i-1); 
			while(l<=r){
				mid=(l+r)/2;
				if(Eok(i,mid)) l=mid+1,ans=max(ans,2*mid);
				else r=mid-1;
			}
		}
		cout<<"Case "<<++cs<<": "<<ans<<endl;
	}
	return 0;
}

TE而亡qwq