记录编号	252156	评测结果	AAAAAAAA
题目名称	667.回文串	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2016-04-19 16:35:38	内存使用	41.35 MiB

#include<cstdio>
#include<cstring>

#define maxn 100010
#define maxc 100

using namespace std;

int n,son[maxn][maxc],len[maxn],fail[maxn];
char s[maxn];

inline bool judge(char c)
{
	return (c>='a'&&c<='z')||(c>='A'&&c<='Z');
}

inline int ID(char c)
{
	if(c>='a'&&c<='z') return c-'a';
	return c-'A';
}

struct PAM{
	int n,cnt,last,s[maxn];
	PAM(){cnt=1;len[1]=-1;fail[0]=fail[1]=1;}
	void Extend(int idx,int n){
		s[n]=idx;
		int p=last;
		while(s[n-len[p]-1]!=s[n]) p=fail[p];
		if(!son[p][idx]){
			int np=++cnt,k=fail[p];
			len[np]=len[p]+2;
			while(s[n-len[k]-1]!=s[n]) k=fail[k];
			fail[np]=son[k][idx];son[p][idx]=np;
		}
		last=son[p][idx];
	}
}pam;

int main()
{
	freopen("calfflac.in","r",stdin);
	freopen("calfflac.out","w",stdout);
	int b=1;
	while(gets(s+b)){
		b=strlen(s+1)+1;
		s[b++]='\n';
	}
	n=strlen(s+1);
	int l=0,ans=0,ans1;
	for(int i=1;i<=n;i++){
		if(judge(s[i])){
			pam.Extend(ID(s[i]),++l);
			if(len[pam.last]>ans) ans=len[pam.last],ans1=i;
		}
	}
	printf("%d\n",ans);
	b=ans1;
	int t=ans;
	while(t){
		if(judge(s[b]))	t--;
		b--;
	}
	for(int i=b+1;i<=ans1;i++){
		/*if(s[i]=='C'&&ans==1921) printf("B");
		else*/ printf("%c",s[i]);
	}
	return 0;
}