rt，在VJudge上Wrong answer on test 2，会不会是Manacher挂了。。。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,n,p[N];
char s[N],t[N];
int Manacher(int x,int y){
	if(x==y)return 1;
	int n=0,r=0,res=0,mi=0;
	memset(p,0,sizeof(p));
	t[++n]='!',t[++n]='#';
	if(x<=y)
		for(int i=x;i<=y;i++)
			t[++n]=s[i],t[++n]='#';
	else for(int i=x;i>=y;i--)
			t[++n]=s[i],t[++n]='#';
	t[++n]='!';
	for(int i=2;i<n;i++){
		if(i<=r)p[i]=min(p[2*mi-i],r-i+1);
		else p[i]=1;
		while(i-p[i]>0&&t[i-p[i]]==t[i+p[i]])p[i]++;
		if(i+p[i]>r)mi=i,r=i+p[i]-1;
		if(i-p[i]==1)res=max(res,p[i]);
	}
	return res-1;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",s+1);n=strlen(s+1);
		int k=0;
		while(s[k+1]==s[n-k] && k+1<n-k)k++;
		for(int i=1;i<=k;i++)cout<<s[i];
		int pre=Manacher(k+1,n-k),suf=Manacher(n-k,k+1);
		if(pre>=suf)
			for(int i=k+1;i<=k+pre;i++)cout<<s[i];
		else for(int i=n-k-suf+1;i<=n-k;i++)cout<<s[i];
		for(int i=n-k+1;i<=n;i++)cout<<s[i];
		cout<<endl;
	}
	return 0;
} 

附：如果不加第七行，输入1 a，输出空行！