FFT通配符匹配

通配符匹配

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
namespace FFTmatch
{
    static const double PI=acos(-1);
    static const double eps=0.5;
    struct Complex
    {
        double x,y;
        Complex(double X=0.0,double Y=0.0):x(X),y(Y) {}
        inline friend Complex operator + (Complex a,Complex b) {return Complex(a.x+b.x,a.y+b.y);}
        inline friend Complex operator - (Complex a,Complex b) {return Complex(a.x-b.x,a.y-b.y);}
        inline friend Complex operator * (Complex a,Complex b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
        template<typename T> inline friend Complex operator / (Complex a,T b) {return Complex(a.x/b,a.y/b);} 
    };
    using VI=vector<int>;
    using VC=vector<Complex>;
    int rev[MAX],revnow;
    inline int Sup(int N)  {int K=0; while((1<<K)<N) ++K; return K;}
    inline void Rea(int K) {if(K==revnow) return; rev[0]=0; for(int i=1;i<=(1<<K);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(K-1));}
    inline void DFT(VC &F,int K,int typ)
    {
        int N=1<<K;
        for(int i=0;i<N;++i) if(rev[i]>i) Swp(F[i],F[rev[i]]);
        for(int len=2,l=1;len<=N;len<<=1,l<<=1)
        {
            Complex stp(cos(2*PI/len),sin(typ*2*PI/len));
            for(int st=0;st<N;st+=len)
            {
                Complex omega(1,0),U,V;
                for(int i=0;i<l;++i)
                    U=F[st+i],V=omega*F[st+i+l],
                    F[st+i]=U+V,F[st+i+l]=U-V,
                    omega=omega*stp;
            }
        }
        if(typ==-1) for(int i=0;i<N;++i) F[i]=F[i]/N;
    }
    inline VI solve(char *a,char *b)
    {
        int n=strlen(a),m=strlen(b),N=n+m-1;
        int K=Sup(N); Rea(K);
        VI A,B,ans; VC F,G,H;
        F.resize(1<<K),G.resize(1<<K),H.resize(1<<K);
        for(int i=0;i<n;++i) A.eb(a[i]=='*'?0:a[i]-'a'+1);
        for(int i=0;i<m;++i) B.eb(b[i]=='*'?0:b[i]-'a'+1);
        reverse(A.begin(),A.end());
        for(int i=n;i<(1<<K);++i) A.eb(0);
        for(int i=m;i<(1<<K);++i) B.eb(0);
        for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i]*A[i]*A[i],0),G[i]=Complex(B[i],0);
        DFT(F,K,1),DFT(G,K,1);
        for(int i=0;i<(1<<K);++i) H[i]=H[i]+F[i]*G[i];
        for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i],0),G[i]=Complex(B[i]*B[i]*B[i],0);
        DFT(F,K,1),DFT(G,K,1);
        for(int i=0;i<(1<<K);++i) H[i]=H[i]+F[i]*G[i];
        for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i]*A[i],0),G[i]=Complex(B[i]*B[i],0);
        DFT(F,K,1),DFT(G,K,1);
        for(int i=0;i<(1<<K);++i) H[i]=H[i]-F[i]*G[i]*Complex(2,0);
        DFT(H,K,-1);
        for(int i=n-1;i<m;++i) if(fabs(H[i].x)<=eps) ans.eb(i-n+2);
        return ans; 
    }
}