一直WA 70分,WA 了1,3,4,5,6,9。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,mod=998244353,G=3,Gi=332748118;
int S,l,cnt[N];
int kuai(int a,int b){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*a*ans%mod;
return ans;
}
void NTT(int *A,int T){
for(int i=0;i<S;i++)if(i>cnt[i])swap(A[i],A[cnt[i]]);
for(int mid=1;mid<S;mid<<=1){
int W=kuai(T?G:Gi,(mod-1)/(mid*2));
for(int L=0;L<S;L+=mid*2){
int now=1;
for(int k=0;k<mid;k++,now=1ll*now*W%mod){
int x=A[L+k],y=1ll*A[L+k+mid]*now%mod;
A[L+k]=(x+y)%mod;
A[L+k+mid]=((x-y)%mod+mod)%mod;
}
}
}
}
int A[N],B[N];
void mul(int *a,int *b,int *ans,int n,int m){
for(l=0,S=1;S<=n+m;S*=2,l++);
for(int i=0;i<=S;i++)A[i]=a[i];
for(int i=0;i<=S;i++)B[i]=b[i];
for(int i=1;i<=S;i++)cnt[i]=(cnt[i>>1]>>1)+((i&1)<<(l-1));
NTT(A,1),NTT(B,1);
for(int i=0;i<=S;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,0);
int Inv=kuai(S,mod-2);
for(int i=0;i<=n+m;i++)ans[i]=1ll*A[i]*Inv%mod;
}
int n,m,a[4][N],b[4][N],ans1[N],ans2[N],ans3[N],ans[N];
vector<int> vec;
char st[N];
int main(){
scanf("%d%d",&n,&m);
scanf("%s",st);
for(int i=0;i<n;i++){
if(st[i]=='*')b[1][i]=0;
else b[1][i]=st[i]-'a'+1;
}
scanf("%s",st);
for(int i=0;i<m;i++){
if(st[i]=='*')a[1][m-i-1]=0;
else a[1][m-i-1]=st[i]-'a'+1;
}
for(int i=0;i<n;i++){
b[2][i]=b[1][i]*b[1][i];
b[3][i]=b[2][i]*b[1][i];
}
for(int i=0;i<m;i++){
a[2][i]=a[1][i]*a[1][i];
a[3][i]=a[2][i]*a[1][i];
}
n--,m--;
mul(a[3],b[1],ans1,m,n);
mul(a[2],b[2],ans2,m,n);
mul(a[1],b[3],ans3,m,n);
for(int i=0;i<S;i++)ans[i]=((ans1[i]-2ll*ans2[i]%mod+mod)%mod+ans3[i])%mod;
n++,m++;
for(int i=n-1;i<m;i++)if(!ans[i])vec.push_back(i-n+2);
printf("%d\n",vec.size());
for(int i:vec)printf("%d ",i);
}