传送门
fftfftfft套路题。
我们把aaa ~ zzz映射成111 ~ 262626，然后把∗*∗映射成000。
考虑对于两个长度都为nnn的字符串A,BA,BA,B。
我们定义一个差异函数dist(A,B)=∑i=1n(ai−bi)2aibidist(A,B)=\sum_{i=1}^n(a_i-b_i)^2a_ib_idist(A,B)=∑i=1n(ai−bi)2aibi其中a,ba,ba,b是A,BA,BA,B的字符的映射值。
然后如果dist(A,B)=0dist(A,B)=0dist(A,B)=0说明两个字符串可以匹配。
然后我们用000把原题中给出的第一个字符串的长度补成nnn，再翻转一下。
然后将两个序列卷积一下可以求出对于第二个串匹配起点在1,2,...n−m+11,2,...n-m+11,2,...n−m+1时分别的distdistdist值。
只需要看哪些位是000就行了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const double pi=acos(-1.0);
const int N=2e6+5;
int tim=0,lim=1,n,m,A[N],B[N],pos[N];
ll sum[N];
vector<int>ans;
char s[N];
struct Complex{
double x,y;
inline Complex operator+(const Complex&b){return (Complex){x+b.x,y+b.y};}
inline Complex operator-(const Complex&b){return (Complex){x-b.x,y-b.y};}
inline Complex operator*(const Complex&b){return (Complex){x*b.x-y*b.y,y*b.x+b.y*x};}
inline Complex operator/(const double&b){return (Complex){x/b,y/b};}
}a[N],b[N];
inline void fft(Complex *a,int type){
for(ri i=0;i<lim;++i)if(i<pos[i])swap(a[i],a[pos[i]]);
for(ri mid=1;mid<lim;mid<<=1){
Complex wn=(Complex){cos(pi/mid),type*sin(pi/mid)};
for(ri j=0,len=mid<<1;j<lim;j+=len){
Complex w=(Complex){1,0};
for(ri k=0;k<mid;++k,w=w*wn){
Complex a0=a[j+k],a1=w*a[j+k+mid];
a[j+k]=a0+a1,a[j+k+mid]=a0-a1;
}
}
}
if(type==-1)for(ri i=0;i<lim;++i)a[i]=a[i]/lim;
}
inline void solve1(){
for(ri i=0;i<=n;++i)a[i].x=A[i]*A[i]*A[i],b[i].x=B[i];
fft(a,1),fft(b,1);
for(ri i=0;i<lim;++i)a[i]=a[i]*b[i];
fft(a,-1);
for(ri i=0;i<lim;++i)sum[i]+=(ll)(a[i].x+0.5),a[i].x=a[i].y=b[i].x=b[i].y=0;
}
inline void solve2(){
for(ri i=0;i<=n;++i)a[i].x=A[i]*A[i],b[i].x=B[i]*B[i],a[i].y=b[i].y=0;
fft(a,1),fft(b,1);
for(ri i=0;i<lim;++i)a[i]=a[i]*b[i];
fft(a,-1);
for(ri i=0;i<lim;++i)sum[i]-=2ll*(ll)(a[i].x+0.5),a[i].x=a[i].y=b[i].x=b[i].y=0;
}
inline void solve3(){
for(ri i=0;i<=n;++i)a[i].x=A[i],b[i].x=B[i]*B[i]*B[i],a[i].y=b[i].y=0;
fft(a,1),fft(b,1);
for(ri i=0;i<lim;++i)a[i]=a[i]*b[i];
fft(a,-1);
for(ri i=0;i<lim;++i)sum[i]+=(ll)(a[i].x+0.5),a[i].x=a[i].y=b[i].x=b[i].y=0;
}
int main(){
int ml;
scanf("%d%d",&m,&n),ml=m+n,--m,--n;
scanf("%s",s);
for(ri i=0;i<=m;++i)A[i]=s[i]=='*'?0:s[i]-'a'+1;
reverse(A,A+m+1);
scanf("%s",s);
for(ri i=0;i<=n;++i)B[i]=s[i]=='*'?0:s[i]-'a'+1;
while(lim<=ml)lim<<=1,++tim;
for(ri i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
solve1(),solve2(),solve3();
for(ri i=m,j=1;i<=n;++i,++j)if(!sum[i])ans.push_back(j);
printf("%d\n",ans.size());
for(ri i=0;i<ans.size();++i)printf("%d ",ans[i]);
return 0;
}