样例过不了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int t,r,mid,cnt,p[3000002];
char a[1000002],c[3000002];
bool mark[3000002];

void read() {
	char ch=getchar();
	while(ch<'a' || ch>'z') ch=getchar();
	while(ch>='a' && ch<='z') {
		ch=getchar();
		c[++cnt]=ch;
		c[++cnt]='#';
	}
}

void manacher() {
	c[0]='~';
	c[1]='#';
	cnt=1;
	read();
	c[cnt+1]='%';
	r=mid=0;
	for(int i=1;i<=cnt;i++) {
		p[i]=0;
		if(i<=r) p[i]=min(p[mid*2-i],r-i+1);
		while(c[i-p[i]]==c[i+p[i]]) p[i]++;
		if(i+p[i]-1>r) {
			r=i+p[i]-1;
			mid=i;
		}
	}
}

int main() {
	scanf("%d",&t);
	while(t--) {
		manacher();
		memset(mark,0,sizeof(mark));
		for(int i=cnt;i;i--) {
			if(i+p[i]-1==cnt) mark[i]=1;
			else if(i-p[i]+1==1 && mark[i+p[i]-2]) mark[i]=1;
		}
		for(int i=2;i<=cnt;i+=2) 
			if(mark[i]) printf("%d ",i/2);
		printf("\n");
	}
	return 0;
}