P5446求调

#include<bits/stdc++.h>
using namespace std;
char s1[4000005],s2[4000005],a;
int p[4000005],l=0,ll,r=0,ans[4000005],l1=0,t,l2;
bool f[4000005];
signed main(){
	cin>>t;
	while(t--){
		cin>>s2+1;
		memset(p,0,sizeof(p));memset(f,0,sizeof(f));
		l=r=ll=l1=0;
		int lll=strlen(s2+1);
		l1++;
		s1[0]='~';
		s1[l1]='#';
		for(int i=1;i<=lll;i++){
			s1[++l1]=s2[i];
			s1[++l1]='#';
		}s1[l1+1]='%';
		for(int i=1;i<=l1;i++){
			if(i<=r){
				p[i]=min(r-i+1,p[l+r-i]);
			}
			while(i-p[i]>=1&&i+p[i]<=l1&&s1[i+p[i]]==s1[i-p[i]]){
				p[i]++;
			}
			if(i+p[i]>r){
				l=i-p[i]+1;
				r=i+p[i]-1;
			}
		}
	//	for(int i=1;i<=l1;i++){
		//	cout<<s1[i];
	//	}cout<<endl;
		for(int i=l1;i>=1;i--){
			f[i]=(f[i+p[i]-2]||(i+p[i]-1==l1));
		//	cout<<i<<' '<<p[i]<<' '<<i+p[i]-1<<' '<<f[i]<<endl;
			if(f[i]&&s1[i]>='a'&&s1[i]<='z'){
				ll++;
				ans[ll]=i/2;
			}
		}
		sort(ans+1,ans+1+ll);
		for(int i=1;i<=ll;i++){
			cout<<ans[i]<<' ';
		}
		cout<<endl;
	}
} 

记录点这里