不知为啥Wa了最后两个点,换模数也没用。
/*
3 7
a*b
aebr*ob
*/
# include <bits/stdc++.h>
using namespace std;
namespace fastio{
template<typename tn> void read(tn &a){
tn x=0,f=1;char c=' ';
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar() ) x=x*10+c-'0';
a=x*f;
}
template<typename tn> void print(tn a){
if(a<0) putchar('-'),a=-a;
if(a>9) print(a/10);
putchar(a%10+'0');
}
};
#define ll long long
using namespace fastio;
const int N=6e5+5;
int n,m;
const int mod=167772161,g=3;
class Array{
private:
vector<int>a;
public:
Array(const int size,const int f):a(size,f){}
void push(int n){a.push_back(n);}
Array(int* l=NULL,int* r=NULL){while(l!=r)push(*l),++l;}
inline int size(){return a.size();}
inline int& operator [] (const int x){return a[x];}
void resize(int n){a.resize(n);}
void clear(){a.clear();}
void swap(){reverse(a.begin(),a.end());}
};
int poww(int a,int b,int mod){
int ans=1;
while(b){
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int* NTT(const int len,Array& a,const bool Ty,int* r=NULL){
if(!r){
r=new int[len];
r[0]=0;int L=log2(len);
for(int i=0;i<len;i++)
r[i]=(r[i>>1]>>1)|((i&1)<<L-1);
}
for(int i=0;i<len;i++)
if(i<r[i])swap(a[i],a[r[i]]);
for(int i=1;i<len;i<<=1){
int T=poww(Ty?g:poww(g,mod-2,mod),(mod-1)/(i<<1),mod);
for(int W=i<<1,j=0;j<len;j+=W){
ll omega=1;
for(int k=0;k<i;++k,omega=omega*T%mod){
ll x(a[j+k]),y(omega*a[i+j+k]%mod);
a[j+k]=x+y;(a[j+k]>mod)&&(a[j+k]-=mod);
a[i+j+k]=x-y+mod;(a[i+j+k]>mod)&&(a[i+j+k]-=mod);
}
}
}
return r;
}
Array Mul(Array x,Array y){
int n=x.size()-1,m=y.size()-1;
int limit=1;
while(limit<=n+m)limit<<=1;
Array ans;
x.resize(limit+1);
y.resize(limit+1);
int *r;
r=NTT(limit,x,1);
NTT(limit,y,1,r);
for(int i=0;i<=limit;i++) x[i]=1ll*x[i]*y[i]%mod;
NTT(limit,x,0,r);
int tem=poww(limit,mod-2,mod);
for(int i=0;i<=n+m;i++) x[i]=(ll)x[i]*tem%mod;
x.resize(n+m+1);
return x;
}
Array a,b;
int main(){
read(m);read(n);
for(int i=0;i<m;i++){
char c=getchar();
if(c!='*') a.push(c-'a'+1);
else a.push(0);
}
getchar();
for(int i=0;i<n;i++){
char c=getchar();
if(c!='*') b.push(c-'a'+1);
else b.push(0);
}
a.swap();
a.resize(n);
Array a1=a;
for(int i=0;i<a1.size();i++) a1[i]=a1[i]*a1[i]*a1[i];
Array f1=Mul(a1,b);
Array b1=b;
for(int i=0;i<b1.size();i++) b1[i]=b1[i]*b1[i]*b1[i];
Array f2=Mul(a,b1);
Array a2=a,b2=b;
for(int i=0;i<a2.size();i++) a2[i]=a2[i]*a2[i];
for(int i=0;i<b2.size();i++) b2[i]=b2[i]*b2[i];
Array f3=Mul(a2,b2);
Array f=f1;
for(int i=0;i<f.size();i++) f[i]=1ll*(f[i]+f2[i])%mod;
for(int i=0;i<f.size();i++) f[i]=1ll*(f[i]-2ll*f3[i]%mod+mod)%mod;
int ans=0;
queue<int> q;
for(int i=m-1;i<n;i++) if(f[i]==0) ans++,q.push(i-m+2);
printf("%d\n",ans);
while(q.size()){
printf("%d ",q.front());
q.pop();
}
return 0;
}