记录编号	560693	评测结果	AAAA
题目名称	[POJ 3974]最长回文子串	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.326 s
提交时间	2021-05-06 21:10:38	内存使用	27.23 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2000005;
char S[maxn],s[maxn];
const int p = 131;
int T = 0;
int hash[maxn],pw[maxn],rev[maxn],rpw[maxn];
void work(void) {
	memset(hash , 0 , sizeof(hash));
	memset(pw , 0 , sizeof(pw));
	memset(rev , 0 , sizeof(rev));             
	memset(rpw , 0 , sizeof(rpw));
	memset(s , 0 , sizeof(s));
	int len = strlen(S + 1);//manacher
	for(int i = 1;i <= len * 2 + 1;++ i) {
		if(i & 1) {
			s[i] = '*';
		}
		else {              
			s[i] = S[i >> 1];
		}
	}
	len = len * 2 + 1;
	pw[0] = 1;
	for(int i = 1;i <= len;++ i) {
		hash[i] = hash[i - 1] * p + (unsigned long long)s[i];
		pw[i] = pw[i - 1] * p;                   
	}
	pw[len + 1] = 1;        
	for(int i = len;i;-- i) {
		rev[i] = rev[i + 1] * p + (unsigned long long)s[i];
	}
	int ans = 1;
	for(int i = 2;i < len;++ i) {
		int lena = min(i , len - i + 1);
		int l = 1,r = lena;              
		while(l <= r) {
			int mid = l + r >> 1;
			if(hash[i] - hash[i - mid] * pw[mid]
			== rev[i] - rev[i + mid] * pw[mid]) {
				l = mid + 1;
			}
			else r = mid - 1;
		}                                                             
		r = (r * 2 - 1) / 2;
		ans = max(ans , r);
	}
	printf("Case %d: %d\n",++T,ans);
	return ;
}
int main() {
	freopen("palindrome.in","r",stdin);
	freopen("palindrome.out","w",stdout);
	while(~ scanf("%s",S + 1)) {
		if(S[1] == 'E')break ;
		work();
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}