记录编号	414146	评测结果	AAAAAAAAAAA
题目名称	[BZOJ 4503] 你猜是不是KMP	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.973 s
提交时间	2017-06-13 15:40:28	内存使用	14.79 MiB

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=1<<18|7;
const double Pi=acos(-1.0);
struct Vec {
	double x,y;
	Vec operator + (const Vec &a){return (Vec){x+a.x,y+a.y};}
	Vec operator - (const Vec &a){return (Vec){x-a.x,y-a.y};}
	Vec operator * (const Vec &a){return (Vec){x*a.x-y*a.y,x*a.y+y*a.x};}
	Vec operator * (const double &a){return (Vec){x*a,y*a};}
	Vec Get(bool b){return (Vec){x,b?-y:y};}
}c[maxn],c1[maxn],w[maxn];int rev[maxn],n,Fu;double Inv;
void FFt(int N){
	int len=0,i;n=1;
	while(n<N)n<<=1,len++;len--;Fu=n-1,Inv=1./n;
	for(i=0;i<n;i++)
		rev[i]=rev[i>>1]>>1|((i&1)<<len),
		w[i]=(Vec){cos(2*Pi/n*i),sin(2*Pi/n*i)};
}
void FFt(Vec *a,bool op){
	int i,j,k;Vec t;
	for(i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(k=2;k<=n;k<<=1)
	for(j=0;j<n;j+=k)
	for(i=0;i<(k>>1);i++)
		t=a[i+j+(k>>1)]*w[n/k*i].Get(op),a[i+j+(k>>1)]=a[i+j]-t,a[i+j]=a[i+j]+t;
	if(op)for(i=0;i<n;i++)a[i]=a[i]*Inv;
}
int len1,len2,cot=0,st[maxn];char S[maxn],T[maxn];
int main(){
	freopen("guess.in","r",stdin);freopen("guess.out","w",stdout);
	scanf("%s%s",S,T);len2=strlen(S),len1=strlen(T);
	FFt(len2+len1);reverse(T,T+len1);int i,j,t3=0;
	for(i=0;i<len2;i++)S[i]-='a'-1;
	for(i=0;i<len1;i++){
		if(T[i]=='?')T[i]=0;else T[i]-='a'-1;
		t3+=T[i]*T[i]*T[i];
	}
	for(i=0;i<n;i++)c[i]=(Vec){S[i]*S[i],T[i]};
	FFt(c,0);Vec v=(Vec){0.5,0}*(Vec){0,-0.5};
	for(i=0;i<n;i++)
		j=(n-i)&Fu,c1[i]=(c[i]+c[j].Get(1))*(c[i]-c[j].Get(1))*v;
	for(i=0;i<n;i++)c[i]=(Vec){S[i],T[i]*T[i]};
	FFt(c,0);v=v*2;
	for(i=0;i<n;i++)
		j=(n-i)&Fu,c1[i]=c1[i]-((c[i]+c[j].Get(1))*(c[i]-c[j].Get(1))*v);
	FFt(c1,1);
	for(i=0;i+len1<=len2;i++)if(t3+round(c1[i+len1-1].x)==0)st[++cot]=i;
	printf("%d\n",cot);
	for(i=1;i<=cot;i++)printf("%d\n",st[i]);
}