#include<bits/stdc++.h>
using namespace std;
char a[11000005],s[22000200];
int r[22000200],v[22000200],ls;
void manacher(){
	scanf("%s",a);
	s[0]=s[1]='#';
	int i,j;
	for(i=0,j=2;a[i];i++,j+=2){
		s[j]=a[i];
		s[j+1]='#';
	}
	s[j+2]='\0';
	ls=strlen(s-1);
	int mid=1,maxright=1;
	for(int i=2;s[i];i++){
		if(i<maxright){
			r[i]=min(r[(mid<<1)-i],maxright-i);
		}else r[i]=1;
		while(s[i-r[i]]==s[i+r[i]]) r[i]++;
		if(i+r[i]>maxright){
			mid=i;
			maxright=i+r[i];
		}
	}
//此处 
//怎么 
//修改 
}
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		memset(r,0,sizeof(r));
		memset(v,0,sizeof(v));
		manacher();
	}
	return 0;
}

题目P5446manacher算法
求写注释部分