记录编号	107197	评测结果	AAAAAAAA
题目名称	回文串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-06-23 10:36:26	内存使用	0.62 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZES=40010;
string text="\0",valid="\0";
int pos[SIZES]={0};//valid[i]在哪
int P[SIZES]={0};//以其为中心的最长回文半径
void Manacher(string &s){
	int mx=0,id=0;
	P[0]=1;
	for(int i=1;i<s.size();i++){
		if(mx>i) P[i]=min(P[2*id-i],mx-i);
		else P[i]=1;
		while(s[i-P[i]]==s[i+P[i]]) P[i]++;
		if(i+P[i]>mx){
			mx=i+P[i];
			id=i;
		}
	}
}
void answer(void){
	int id=0;
	for(int i=1;i<valid.size();i++) if(P[i]>P[id]) id=i;
	printf("%d\n",P[id]-1);
	int l=id-P[id]+1,r=id+P[id]-1;
	while(valid[l]=='#') l++;
	while(valid[r]=='#') r--;
	for(int i=pos[l];i<=pos[r];i++) printf("%c",text[i]);
}
void read(void){
	char c;
	while(scanf("%c",&c)!=EOF){
		text+=c;
		if(('a'<=c&&c<='z')||('A'<=c&&c<='Z')){
			if('A'<=c&&c<='Z') c+='a'-'A';
			valid+='#';
			valid+=c;
			pos[valid.size()-1]=text.size()-1;
		}
	}
	valid+='#';
}
int main(){
	freopen("calfflac.in","r",stdin);
	freopen("calfflac.out","w",stdout);
	read();
	Manacher(valid);
	answer();
	return 0;
}