题目概述

有两个串 $A,B$ ，有些位置是通配符，求 $A$ 可以在 $B$ 的哪些位置匹配。

解题报告

早就听说了这题，今天来填坑。判断两个字符串相等可以用式子：$\sum_{i=0}^{len}(A_i-B_i)^2=0$ ，但是有通配符，所以可以把通配符给 $0$ ，然后式子变成这样：$\sum_{i=0}^{len}(A_i-B_i)^2A_iB_i=0$ 。

对于 $B$ 的每个开头 $i$ ，展开来是这样的：

$$ sum_i=\sum_{j=0}^{|A|}A_j^3B_{i+j}-2A_j^2B_{i+j}^2+A_iB_{i+j}^3\\ sum_i=\sum_{k-j=i}A_j^3B_k-2A_j^2B_k^2+A_jB_k^3\\ sum_{i+|B|}=\sum_{k+j=i+|B|}A_{|B|-j}^3B_k-2A_{|B|-j}^{2}B_k^2+A_{|B|-j}B_k^3 $$

这是？三个卷积？把 $A$ 补成 $B$ 的长度，然后套三次FFT就行啦。

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;typedef double DB;typedef pair<DB,DB> CN;
const int maxn=300000,maxm=1<<20;const DB pi=acos(-1);

int A,B,n,m,rev[maxm+5];char a[maxn+5],b[maxn+5];CN f[maxm+5],g[maxm+5];int ans;LL sum[maxn+5];

inline CN operator + (const CN &a,const CN &b) {return mp(a.fr+b.fr,a.sc+b.sc);}
inline CN operator - (const CN &a,const CN &b) {return mp(a.fr-b.fr,a.sc-b.sc);}
inline CN operator * (const CN &a,const CN &b) {return mp(a.fr*b.fr-a.sc*b.sc,a.fr*b.sc+a.sc*b.fr);}
inline void Rev(int n,int len) {for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<len-1);}
inline void FFT(CN *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        CN wn=mp(cos(pi/k),f*sin(pi/k)),w=mp(1,0),x,y;
        for (int i=0;i<n;i+=k<<1,w=mp(1,0))
            for (int j=0;j<k;j++,w=w*wn)
                x=a[i+j],y=a[i+j+k]*w,a[i+j]=x+y,a[i+j+k]=x-y;
    }if (f<0) for (int i=0;i<n;i++) a[i].fr/=n;
}
int main(){
    scanf("%d%d",&A,&B);A--;B--;n=B;scanf("%s%s",a,b);
    for (int i=0;i<=A;i++) if (a[i]!='*') a[i]=a[i]-'a'+1;for (int i=0;i<=B;i++) if (b[i]!='*') b[i]=b[i]-'a'+1;
    int len=0;for (m=1;m<=(n<<1);m<<=1) len++;Rev(m,len);

    for (int i=0;i<=n;i++) if (a[n-i]!='*') f[i]=mp(a[n-i]*a[n-i]*a[n-i],0); else f[i]=mp(0,0);
    for (int i=0;i<=n;i++) if (b[i]!='*') g[i]=mp(b[i],0); else g[i]=mp(0,0);
    FFT(f,m,1);FFT(g,m,1);for (int i=0;i<m;i++) f[i]=f[i]*g[i];FFT(f,m,-1);
    for (int i=0;i<=n;i++) sum[i]+=LL(f[i+n].fr+0.5);for (int i=0;i<m;i++) f[i]=g[i]=mp(0,0);

    for (int i=0;i<=n;i++) if (a[n-i]!='*') f[i]=mp(a[n-i]*a[n-i],0); else f[i]=mp(0,0);
    for (int i=0;i<=n;i++) if (b[i]!='*') g[i]=mp(b[i]*b[i],0); else g[i]=mp(0,0);
    FFT(f,m,1);FFT(g,m,1);for (int i=0;i<m;i++) f[i]=f[i]*g[i];FFT(f,m,-1);
    for (int i=0;i<=n;i++) sum[i]-=LL(f[i+n].fr+0.5)<<1;for (int i=0;i<m;i++) f[i]=g[i]=mp(0,0);

    for (int i=0;i<=n;i++) if (a[n-i]!='*') f[i]=mp(a[n-i],0); else f[i]=mp(0,0);
    for (int i=0;i<=n;i++) if (b[i]!='*') g[i]=mp(b[i]*b[i]*b[i],0); else g[i]=mp(0,0);
    FFT(f,m,1);FFT(g,m,1);for (int i=0;i<m;i++) f[i]=f[i]*g[i];FFT(f,m,-1);

    for (int i=0;i<=n;i++) sum[i]+=LL(f[i+n].fr+0.5);for (int i=0;i<=B-A;i++) ans+=!sum[i];printf("%d\n",ans);
    for (int i=0,fst=true;i<=B-A;i++) if (!sum[i]) fst?fst=false:putchar(' '),printf("%d",i+1);puts("");return 0;
}