【笔记】带通配符字符串匹配

题目描述

给你两个带通配符的串 $A,B$。问 $B$ 中可以匹配多少个 $A$，并输出匹配的开头位置。

思路

我们在两个长度相同的字符串 $A, B$ 上定义 $f(A, B)=\sum_{i=0}^{n-1}(A_i – B_i)^2A_iB_i$。令通配符 * 为 0，当 $f(A,B)=0$ 时，$A = B$。

将 $f$ 展开得 $\sum_{i=0}^{n-1} \left( {A_i}^3B_i – 2 {A_i}^2{B_i}^2 + A_i{B_i}^3 \right)$。

我们将 $A$ 翻转得到 $A’$，那么上式等于 $\sum_{i=0}^{n-1} ( {A’_{n-i-1}}^3B_i – 2 {A’_{n-i-1}}^2{B_i}^2 + A’_{n-i-1}{B_i}^3)$，就将这个式子变换成为了卷积的形式。

做七遍 FFT ，输出所有答案为 $0$ 的下标即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+1;
const double PI=acos(-1.0);

struct cd{
    double x,y;
    inline cd (double x_=0,double y_=0):x(x_),y(y_){}
    inline cd operator + (const cd &b) const{return cd(x+b.x,y+b.y);};
    inline cd operator - (const cd &b) const{return cd(x-b.x,y-b.y);};
    inline cd operator * (const cd &b) const{return cd(x*b.x-y*b.y,x*b.y+y*b.x);}
    inline cd operator / (const double &b) const{return cd(x/b,y/b);};
};

int n,m,s,bit,rev[maxn];

void init(){
    for (bit=1,s=2;(1<<bit)<2*n;++bit) s<<=1;
    for (int i=0;i<s;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}

void fft(cd *a,int n,int dft){
    for (int i=0;i<n;++i)
    if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int step=1;step<n;step<<=1){
        cd wn(cos(PI/step),dft*sin(PI/step));
        for (int j=0;j<n;j+=step<<1){
            cd wnk(1,0);
            for (int k=j;k<j+step;++k,wnk=wnk*wn){
                cd t=wnk*a[k+step];
                a[k+step]=a[k]-t;
                a[k]=a[k]+t;
            }
        }
    }
    if (dft==-1) for (int i=0;i<n;++i) a[i]=a[i]/(double)n;
}

cd a2[maxn],b2[maxn],c[maxn];
int a[maxn],b[maxn];
char s1[maxn],s2[maxn];
queue<int>q;

int main(){
    scanf("%d%d%s%s",&m,&n,s1,s2);
    init();
    for (int i=0;i<m;++i)
    if (s1[m-i-1]!='*') a[i]=s1[m-i-1]-'a'+1;
    for (int i=0;i<n;++i)
    if (s2[i]!='*') b[i]=s2[i]-'a'+1;

    for (int i=0;i<m;++i) a2[i]=cd(a[i]*a[i]*a[i],0);
    for (int i=0;i<n;++i) b2[i]=cd(b[i],0);
    fft(a2,s,1),fft(b2,s,1);
    for (int i=0;i<s;++i) c[i]=c[i]+a2[i]*b2[i];
    for (int i=0;i<s;++i) a2[i]=b2[i]=cd(0,0);

    for (int i=0;i<m;++i) a2[i]=cd(a[i]*a[i],0);
    for (int i=0;i<n;++i) b2[i]=cd(b[i]*b[i],0);
    fft(a2,s,1),fft(b2,s,1);
    for (int i=0;i<s;++i) c[i]=c[i]-a2[i]*b2[i]-a2[i]*b2[i];
    for (int i=0;i<s;++i) a2[i]=b2[i]=cd(0,0);

    for (int i=0;i<m;++i) a2[i]=cd(a[i],0);
    for (int i=0;i<n;++i) b2[i]=cd(b[i]*b[i]*b[i],0);
    fft(a2,s,1),fft(b2,s,1);
    for (int i=0;i<s;++i) c[i]=c[i]+a2[i]*b2[i];

    fft(c,s,-1);
    for (int i=m-1;i<n;++i)
    if (fabs(c[i].x<0.5)) q.push(i-m+2);
    printf("%d\n",q.size());
    while(!q.empty()) printf("%d ",q.front()),q.pop();
}