# 求助QAQ

@niiick 2019-01-08 18:27 回复

WA3 T9实在找不到错了QAQ， 蒟蒻几乎都照着题解抄了

#include<iostream>
#include<cmath>
#include<algorithm>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;
typedef double dd;
#define eps 1e-7

{
int f=1,x=0;
char ss=getchar();
while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
return f*x;
}

const dd Pi=acos(-1.0);
const int maxn=1200010;
int n,m;
struct complex{
dd x,y;
complex(dd _x=0,dd _y=0){ x=_x; y=_y;}
}A[maxn],B[maxn],C[maxn];
int lim=1,L,R[maxn];
char pat[maxn],txt[maxn];
int a[maxn],b[maxn];
int ans[maxn],cnt;

complex operator +(complex a,complex b){ return complex( a.x+b.x, a.y+b.y);}
complex operator -(complex a,complex b){ return complex( a.x-b.x, a.y-b.y);}
complex operator *(complex a,complex b){ return complex( a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}

void FFT(complex* a,int opt)
{
for(int i=0;i<lim;++i)
if(i<R[i]) swap(a[i],a[R[i]]);

for(int i=1;i<lim;i<<=1)
{
complex wn(cos(Pi/i),opt*sin(Pi/i));
for(int j=0;j<lim;j+=(i<<1))
{
complex w(1,0);
for(int k=0;k<i;++k)
{
complex nx=a[j+k],ny=w*a[i+j+k];
a[j+k]=nx+ny;
a[i+j+k]=nx-ny;
w=w*wn;
}
}
}

if(opt==-1)
for(int i=0;i<=lim;++i) a[i].x/=(dd)lim;
}

void solve1()
{
for(int i=0;i<lim;++i)
A[i]=complex(a[i]*a[i]*a[i],0),B[i]=complex(b[i],0);
FFT(A,1);FFT(B,1);
for(int i=0;i<lim;++i) C[i]=C[i]+A[i]*B[i];
}

void solve2()
{
for(int i=0;i<lim;++i)
A[i]=complex(a[i],0),B[i]=complex(b[i]*b[i]*b[i],0);
FFT(A,1);FFT(B,1);
for(int i=0;i<lim;++i) C[i]=C[i]+A[i]*B[i];
}

void solve3()
{
for(int i=0;i<lim;++i)
A[i]=complex(a[i]*a[i],0),B[i]=complex(b[i]*b[i],0);
FFT(A,1);FFT(B,1);
for(int i=0;i<lim;++i) C[i]=C[i]-A[i]*B[i]*complex(2,0);
}

int main()
{
scanf("%s%s",pat,txt);
reverse(pat,pat+n);

while(lim<=n+m-2) lim<<=1,L++;
for(int i=0;i<lim;++i)
R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

for(int i=0;i<n;++i) a[i]=(pat[i]!='*')?(pat[i]-'a'+1):0;
for(int i=0;i<m;++i) b[i]=(txt[i]!='*')?(txt[i]-'a'+1):0;

solve1(); solve2(); solve3();
FFT(C,-1);
for(int i=n-1;i<m;++i)
if(fabs(C[i].x)<eps) ans[++cnt]=i-n+2;

printf("%d\n",cnt);
for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
return 0;
}