记录编号	414922	评测结果	AAAAAAAAAAA
题目名称	[BZOJ 4503] 你猜是不是KMP	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.199 s
提交时间	2017-06-15 11:44:41	内存使用	24.79 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=262200;
const double pi=acos(-1.0),eps=1e-3;
struct Complex{
	double a,b;
	Complex(double a=0.0,double b=0.0):a(a),b(b){}
	Complex operator+(const Complex &x)const{return Complex(a+x.a,b+x.b);}
	Complex operator-(const Complex &x)const{return Complex(a-x.a,b-x.b);}
	Complex operator*(const Complex &x)const{return Complex(a*x.a-b*x.b,a*x.b+b*x.a);}
	Complex operator*(double x)const{return Complex(a*x,b*x);}
}w[maxn],w_inv[maxn],A[maxn],B[maxn],C[maxn],D[maxn];
void FFT_init();
void FFT(Complex*,int,int);
char s[maxn],t[maxn];
int n,m,N;
int main(){
	freopen("guess.in","r",stdin);
	freopen("guess.out","w",stdout);
	scanf("%s%s",s,t);
	n=strlen(s);
	m=strlen(t);
	N=1;
	while(N<n+m)N<<=1;
	FFT_init();
	reverse(t,t+m);
	for(int i=0,x;i<n;i++){
		x=s[i]-'a'+1;
		A[i].a=x*x;
		B[i].a=x;
	}
	double sum=0.0;
	for(int i=0,x;i<m;i++){
		x=(t[i]=='?'?0:t[i]-'a'+1);
		C[i].a=x;
		D[i].a=x*x;
		sum+=x*x*x;
	}
	FFT(A,N,1);
	FFT(B,N,1);
	FFT(C,N,1);
	FFT(D,N,1);
	for(int i=0;i<N;i++)A[i]=A[i]*C[i]-B[i]*D[i]*2.0;
	FFT(A,N,-1);
	int ans=0;
	for(int i=0;i+m-1<n;i++)if(A[i+m-1].a+sum<eps)ans++;
	printf("%d\n",ans);
	for(int i=0;i+m-1<n;i++)if(A[i+m-1].a+sum<eps)printf("%d\n",i);
	return 0;
}
void FFT_init(){
	for(int i=0;i<N;i++){
		w[i]=Complex(cos(2*pi/N*i),sin(2*pi/N*i));
		w_inv[i]=Complex(cos(-2*pi/N*i),sin(-2*pi/N*i));
	}
}
void FFT(Complex *A,int n,int tp){
	for(int i=1,j=0,k;i<n-1;i++){
		k=n;
		do j^=(k>>=1);while(j<k);
		if(i<j)swap(A[i],A[j]);
	}
	for(int k=2;k<=n;k<<=1)for(int i=0;i<n;i+=k)for(int j=0;j<(k>>1);j++){
		Complex a=A[i+j],b=(tp>0?w:w_inv)[N/k*j]*A[i+j+(k>>1)];
		A[i+j]=a+b;
		A[i+j+(k>>1)]=a-b;
	}
	if(tp<0)for(int i=0;i<n;i++)A[i].a/=n;
}