记录编号	251110	评测结果	AAAAAAAAAA
题目名称	[BZOJ 4503] 你猜是不是KMP	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	4.008 s
提交时间	2016-04-16 21:26:01	内存使用	36.17 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxn=400010;
const double PI=acos(-1.0);
char s[maxn],t[maxn];
int a[maxn],b[maxn];
struct complex{
	double r,i;
	complex(double r_=0.0,double i_=0.0){
		r=r_;i=i_;
	}
	complex operator +(complex a){
		return complex(r+a.r,i+a.i);
	}
	complex operator -(complex a){
		return complex(r-a.r,i-a.i);
	}
	complex operator *(complex a){
		return complex(r*a.r-i*a.i,r*a.i+i*a.r);
	}
};
complex A[maxn],B[maxn],C[maxn],D[maxn],E[maxn];

void Rader(complex *a,int len){
	int k;
	for(int i=1,j=len>>1;i<len-1;i++){
		if(i<j)swap(a[i],a[j]);
		k=len>>1;
		while(j>=k){
			j-=k;
			k>>=1;
		}
		j+=k;
	}		
}

void FFT(complex *a,int len,int on){
	Rader(a,len);
	for(int h=2;h<=len;h<<=1){
		complex wn(cos(on*PI*2.0/h),sin(on*PI*2.0/h));
		for(int j=0;j<len;j+=h){
			complex w(1,0);
			for(int k=j;k<j+(h>>1);k++){
				complex u=a[k];
				complex v=a[k+(h>>1)]*w;
				a[k]=u+v;
				a[k+(h>>1)]=u-v;
				w=w*wn;
			}
		}
	}
	if(on==-1)
		for(int i=0;i<len;i++)
			a[i].r/=len;	
}
int ans[maxn],tot;
int main(){
	freopen("guess.in","r",stdin);
	freopen("guess.out","w",stdout);
	scanf("%s%s",s,t);
	int lens=strlen(s);
	int lent=strlen(t);
	for(int i=0;i<lens;i++)
		a[i]=s[i]-'a'+1;
	for(int i=0;i<lent;i++){
		if(t[i]=='?')
			b[lent-i-1]=0;
		else
			b[lent-i-1]=t[i]-'a'+1;	
	}
	
	int len=1;
	while(len<lens+lent)len<<=1;
	
	for(int i=0;i<lens;i++)A[i]=complex(1.0,0);
	for(int i=0;i<lent;i++)B[i]=complex(1.0*b[i]*b[i]*b[i],0);
	FFT(A,len,1);FFT(B,len,1);
	for(int i=0;i<len;i++)C[i]=A[i]*B[i];
	FFT(C,len,-1);	
	
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
	for(int i=0;i<lens;i++)A[i]=complex(2.0*a[i],0);
	for(int i=0;i<lent;i++)B[i]=complex(1.0*b[i]*b[i],0);
	FFT(A,len,1);FFT(B,len,1);
	for(int i=0;i<len;i++)D[i]=A[i]*B[i];
	FFT(D,len,-1);
		
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
	for(int i=0;i<lens;i++)A[i]=complex(1.0*a[i]*a[i],0);
	for(int i=0;i<lent;i++)B[i]=complex(1.0*b[i],0);
	FFT(A,len,1);FFT(B,len,1);
	for(int i=0;i<len;i++)E[i]=A[i]*B[i];
	FFT(E,len,-1);
	
	for(int i=lent-1;i<lens;i++)
		if(fabs(C[i].r-D[i].r+E[i].r)<1e-5)
			ans[++tot]=i-lent+1;
		
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
		printf("%d\n",ans[i]);		
	return 0;
}