# 为什么窝的精度损失这么大啊qwq

@kkxhh 2019-03-10 11:54 回复

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

typedef struct complex{
double a,b;
complex() {}
complex(double _a,double _b):a(_a),b(_b) {}
complex operator + (complex x) {return complex(a+x.a,b+x.b);}
complex operator - (complex x) {return complex(a-x.a,b-x.b);}
complex operator * (complex x) {return complex(a*x.a-b*x.b,a*x.b+b*x.a);}
}complex;

const double Pi=acos(-1.0),eps=1e-5;
complex a[1050000],a2[1050000],a3[1050000],b[1050000],b2[1050000],b3[1050000];
int m,n,limit=1,l,r[1050000],ans[300010],siz;
char s[300010];

int num=0,k=1; char c=getchar();
while(c>'9' || c<'0') k=(c=='-')?0:k,c=getchar();
while(c>='0' && c<='9') num=num*10+c-'0',c=getchar();
return k?num:-num;
}

void FFT(complex *a,int type){
for(int i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);
for(int len=1;len<limit;len<<=1){
complex w(cos(Pi/len),type*sin(Pi/len));
for(int i=0;i<limit;i+=(len<<1)){
complex k(1.0,0);
for(int j=0;j<len;j++,k=k*w){
complex x=a[i+j],y=k*a[i+j+len];
a[i+j]=x+y; a[i+j+len]=x-y;
}
}
}
if(type==-1) for(int i=0;i<limit;i++) a[i].a/=limit;
}

int main(){
while(limit<=n+m) limit<<=1,l++;
for(int i=0;i<limit;i++) r[i]=((r[i>>1]>>1)|((i&1)<<(l-1)));
scanf("%s",s);
for(int i=m-1;i>=0;i--) a[i].a=((s[m-1-i]!='*')?(s[m-1-i]-'a'+1):0),a2[i].a=a[i].a*a[i].a,a3[i].a=a2[i].a*a[i].a;
scanf("%s",s);
for(int i=0;i<n;i++) b[i].a=((s[i]!='*')?(s[i]-'a'+1):0),b2[i].a=b[i].a*b[i].a,b3[i].a=b2[i].a*b[i].a;
FFT(a,1); FFT(b,1); FFT(a2,1); FFT(b2,1); FFT(a3,1); FFT(b3,1);
for(int i=0;i<limit;i++) a[i]=(a3[i]*b[i])+(a[i]*b3[i])-(complex(2.0,0)*b2[i]*a2[i]);
FFT(a,-1);
for(int i=m-1;i<=n-1;i++) if(fabs(a[i].a)<=eps) ans[++siz]=i-m+2;
printf("%d\n",siz);
for(int i=1;i<=siz;i++) printf("%d ",ans[i]);
return 0;
}