【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=4503

【题目大意】

    给出S串和T串，计算T在S中出现次数，T中有通配符'?'。

【题解】

    含通配符的字符串匹配问题，FFT的基本运用，解法同 BZOJ4259 。

【代码】

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring> 
using namespace std;
typedef long long LL;
const int N=1048600;
int n,pos[N];
namespace FFT{
    struct comp{
        double r,i;
        comp(double _r=0,double _i=0):r(_r),i(_i){}
        comp operator +(const comp&x){return comp(r+x.r,i+x.i);}
        comp operator -(const comp&x){return comp(r-x.r,i-x.i);}
        comp operator *(const comp&x){return comp(r*x.r-i*x.i,i*x.r+r*x.i);}
        comp conj(){return comp(r,-i);}
    }A[N],B[N];
    const double pi=acos(-1.0);
    void FFT(comp a[],int n,int t){
        for(int i=1;i<n;i++)if(pos[i]>i)swap(a[i],a[pos[i]]);
        for(int d=0;(1<<d)<n;d++){
            int m=1<<d,m2=m<<1;
            double o=pi*2/m2*t;
            comp _w(cos(o),sin(o));
            for(int i=0;i<n;i+=m2){
                comp w(1,0);
                for(int j=0;j<m;j++){
                    comp& A=a[i+j+m],&B=a[i+j],t=w*A;
                    A=B-t;B=B+t;w=w*_w;
                }
            }
        }if(t==-1)for(int i=0;i<n;i++)a[i].r/=n;
    }
}
int l1,l2,ans[N],cnt=0,a[N],b[N];
FFT::comp A[N],B[N],C[N];
char s1[N],s2[N];
int main(){
    scanf(" %s %s",&s1,&s2);
    l1=strlen(s1); l2=strlen(s2);
    for(int i=0;i<l1;i++)a[i]=s1[i]-'a'+1;
    for(int i=0;i<l2;i++)b[l2-1-i]=s2[i]=='?'?0:s2[i]-'a'+1;
    int N=1; while(N<l1+l2)N<<=1;
    int j=__builtin_ctz(N)-1;
    for(int i=0;i<N;i++){pos[i]=pos[i>>1]>>1|((i&1)<<j);} 
    for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i]*a[i],0),B[i]=FFT::comp(b[i],0);
    FFT::FFT(A,N,1);FFT::FFT(B,N,1);
    for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i];
    for(int i=0;i<N;i++)A[i]=FFT::comp(a[i],0),B[i]=FFT::comp(b[i]*b[i]*b[i],0);
    FFT::FFT(A,N,1);FFT::FFT(B,N,1);
    for(int i=0;i<N;i++)C[i]=C[i]+A[i]*B[i];
    for(int i=0;i<N;i++)A[i]=FFT::comp(a[i]*a[i],0),B[i]=FFT::comp(b[i]*b[i],0);
    FFT::FFT(A,N,1);FFT::FFT(B,N,1);
    for(int i=0;i<N;i++)C[i]=C[i]-A[i]*B[i]*FFT::comp(2,0);
    FFT::FFT(C,N,-1);
    for(int i=l2-1;i<l1;i++){
        if(C[i].r<0.5)ans[cnt++]=i-l2+1;
    }printf("%d\n",cnt);
    for(int i=0;i<cnt;i++)printf("%d\n",ans[i]);
    return 0;
}

• 相关文章
• 全局相关文章