WA提交记录

#include<iostream>
#include<cstdio>
using namespace std;
template<typename T>
void read(T& x){
	char c=getchar();bool a=0;x=0;
	while(!isdigit(c)){
		if(c=='-') a=!a;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	if(a) x*=-1;
	return;
}
int input(char* x){
	char c=getchar();int len=1;*x++='#';
	while('a'<=c&&c<='z'){
		*x++=c,*x++='#',len+=2;
		c=getchar();
	}
	*x=0;
	return len;
}
const int N=2e6+10;
bool ans[N];
char s[N];
int len;
int p[N];
void manacher(){
	for(int i=0,l=0,r=-1,k;i<len;i++){
		k=(i<r?p[l+r-i]:1);
		while(i-k>=0&&i+k<len&&s[i-k]==s[i+k]) k++;
		if(i+k>r) l=i-k,r=i+k;
		p[i]=k;
	}
	return;
}
int main(){
	ios::sync_with_stdio(0),cout.tie(0);
	int T;read(T);
	while(T--){
		len=input(s);
		manacher();
		//printf("len=%d\n",len);
		int x=len;
		ans[x-=2]=true;
		while(x-=2,x>=0){
			//printf("s[x]=%c,x=%d,p[x]=%d,",s[x],x,p[x]);
			if(x+p[x]==len||x+1==p[x]&&ans[x+p[x]-2]){
				ans[x]=true;
			}
			//printf("ans=%d\n",ans[x]);
		}
		for(int i=1;i<len;i+=2){
			if(ans[i]) cout<<(i>>1)+1<<" ";
			ans[i]=false;
		}
		cout<<"\n";
	}
	return 0;
}