记录编号	380079	评测结果	AAAAAAAA
题目名称	回文串	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2017-03-08 11:25:20	内存使用	14.21 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
const double INF = 1e60;
const int inf = 0x7f7f7f7f;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 20010*4;

int n,len,cnt,rt,last;
int mp[maxn],num;
struct SAM
{
	int root,next[30],val;
}a[maxn];
void add(int c){
	int p = last, np = ++cnt;
	mp[++num] = cnt;
	a[np].val = a[p].val + 1;
	while(p && a[p].next[c]==0){
		a[p].next[c] = np;
		p = a[p].root;
	}
	if(!p) a[np].root = rt;
	else {
		int q = a[p].next[c];
		if(a[q].val == a[p].val+1) a[np].root = q;
		else {
			int nq = ++cnt;
			a[nq] = a[q];
			a[nq].val = a[p].val+1;
			a[np].root = a[q].root = nq;
			while(p && a[p].next[c]==q){
				a[p].next[c] = nq;
				p = a[p].root;
			}
		}
	}
	last = np;
}
vector<char> C[maxn];
bool flip[maxn];
char s[maxn];
int b[maxn];
vector<int> G[maxn];

int size[maxn],son[maxn],deep[maxn],top[maxn],fa[maxn];

void Dfs1(int x){
	size[x] = 1; son[x] = 0;
	int sz=G[x].size();
	for(int i=0; i<sz; i++){
		int p=G[x][i];
		deep[p] = deep[x]+1;
		Dfs1(p);
		size[x] += size[p];
		if(size[son[x]]<size[p]) son[x]=p;
	}
}
void Dfs2(int x,int tp){
	top[x] = tp; int sz=G[x].size();
	if(son[x]) Dfs2(son[x], tp);
	for(int i=0; i<sz; i++){
		int p=G[x][i];
		if(son[x]!=p) Dfs2(p, p);
	}
}
int tree_lca(int x,int y){
	int fx = top[x], fy = top[y];
	while(fx != fy){
		if(deep[fx] < deep[fy]){ swap(fx, fy); swap(x, y); }
		x = a[fx].root, fx = top[x];
	}
	if(deep[x]>deep[y]) swap(x, y);
	return x;
}
int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("calfflac.in", "r", stdin);
	freopen("calfflac.out", "w", stdout);
#endif
	char ch;
	while(ch=getchar(), ch!=EOF){
		s[++len] = ch;
	}//len--;
	int pa=0;
	for(int i=1; i<=len; i++){
		if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')){
			n++;
			if(s[i]>='a'&&s[i]<='z') b[n] = s[i] - 'a';
			else b[n] = s[i] - 'A', flip[n] = 1;
			pa = n;
		} else {
			C[pa].push_back(s[i]);
		}
	}
	int tmp=n;
	b[++n] = 27; 
	for(int i=tmp; i; i--){
		b[++n] = b[i];
	}
	rt = last = ++cnt;
	for(int i=1; i<=n; i++){
		add(b[i]);
	}
	reverse(mp+1, mp+1+n);
	for(int i=1; i<=cnt; i++){
		int fa=a[i].root;
		G[fa].push_back(i);
	}
	Dfs1(rt);
	Dfs2(rt,rt);

	int res;
	int ans = 0;
	int str;
	for(int i=1; i<=tmp; i++){
		int x = mp[i], y = mp[n-i+1];
		int lca = tree_lca(x, y);
		int lcp = a[lca].val;
		res = lcp*2-1;
		if(res > ans){
			ans = res;
			str = i-lcp+1;
		}
		x = mp[i], y = mp[n-i+2];
		lca = tree_lca(x, y);
		lcp = a[lca].val;
		res = lcp * 2;
		if(res > ans){
			ans = res;
			str = i-lcp;
		}
	}
	printf("%d\n", ans);
	for(int i=0; i<ans; i++){
		int p = i+str;
		if(flip[p]) ch = b[p]+'A';
		else ch = b[p]+'a';
		printf("%c", ch);
		if(i==ans-1) break;
		int sz = C[p].size();
		for(int j=0; j<sz; j++){
			printf("%c", C[p][j]);
		}
	}printf("\n");

	return 0;
}

/*

aabbaa

 */