Luogu

分析

令 * 为 $0$ ，a 为 $1$ ，以此类推；定义 $dis(A,B)=\sum\limits_{i=0}^{n-1}(A_i-B_i)^2A_iB_i$ 。

显然，当且仅当 $dis(A,B)=0$ 时，$A=B$ 。

将 $dis(A, B)$ 展开得到
$$
dis(A,B)=\sum_{i=0}^{n-1}({A_i}^3B_i-2{A_i}^2{B_i}^2+A_i{B_i}^3)
$$
将 $A$ 翻转后 FFT 即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1200000+10;

struct Complex {
    double x,y;
    Complex(double x_=0,double y_=0):x(x_),y(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); }
Complex operator *(Complex a,Complex b) { return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }

int r[N];

inline void FFT(Complex* a,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(a[i],a[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        Complex rot(cos(M_PI/i),op*sin(M_PI/i));
        for (re int j=0;j<n;j+=(i<<1)) {
            Complex w(1,0);
            for (re int k=0;k<i;++k,w=w*rot) {
                Complex x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if (op==-1) {
        for (re int i=0;i<n;++i) a[i].x/=n;
    }
}

char s1[N],s2[N];
int a[N],b[N];
Complex f[N],g[N],ans[N];
int sta[N],top;

int main() {
    int m=read(),n=read(); scanf("%s%s",s1,s2);
    for (re int i=0;i<m;++i) a[i]=(s1[m-i-1]=='*')?0:s1[m-i-1]-'a'+1;
    for (re int i=0;i<n;++i) b[i]=(s2[i]=='*')?0:s2[i]-'a'+1;

    int len=1,l=0;
    for (;len<n+n;len<<=1,++l);
    for (re int i=0;i<len;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

    for (re int i=0;i<m;++i) f[i]=Complex(a[i]*a[i]*a[i]);
    for (re int i=0;i<n;++i) g[i]=Complex(b[i]);
    FFT(f,len,1),FFT(g,len,1);
    for (re int i=0;i<len;++i) ans[i]=f[i]*g[i];

    for (re int i=0;i<m;++i) f[i]=Complex(a[i]*a[i]);
    for (re int i=m;i<len;++i) f[i]=Complex();
    for (re int i=0;i<n;++i) g[i]=Complex(b[i]*b[i]);
    for (re int i=n;i<len;++i) g[i]=Complex();
    FFT(f,len,1),FFT(g,len,1);
    for (re int i=0;i<len;++i) ans[i]=ans[i]-2*f[i]*g[i];

    for (re int i=0;i<m;++i) f[i]=Complex(a[i]);
    for (re int i=m;i<len;++i) f[i]=Complex();
    for (re int i=0;i<n;++i) g[i]=Complex(b[i]*b[i]*b[i]);
    for (re int i=n;i<len;++i) g[i]=Complex();
    FFT(f,len,1),FFT(g,len,1);
    for (re int i=0;i<len;++i) ans[i]=ans[i]+f[i]*g[i];

    FFT(ans,len,-1);
    for (re int i=m-1;i<n;++i)
        if (ans[i].x<0.5) sta[++top]=i-m+2;
    printf("%d\n",top);
    for (re int i=1;i<=top;++i) printf("%d ",sta[i]); puts("");
    return 0;
}