并不对劲的复健训练-有通配符的字符串匹配

àì夳堔傛蜴生んèń 2023-08-17 16:46 51阅读 0赞

[这个人][Link 1]讲得很清楚

关键在于把“匹配”转换成“某个式子的值为0”。

#include<algorithm>
    #include<cmath>
    #include<complex>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];~k;k=nxt[k])
    #define LL long long
    #define cd complex<double>
    #define maxn 2400007
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar(' ');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar(' ');
        return;
    }
    const double pi=acos(-1);
    int l1,l2,r[maxn],len,nown,ans[maxn],num;
    cd a[maxn],b[maxn],A[maxn],B[maxn],c[maxn];
    char s1[maxn],s2[maxn];
    void getlen(int li)
    {
        for(len=0,nown=1;nown<li;nown<<=1,len++);
        rep(i,0,nown-1)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
    }
    void dft(cd * u,double f)
    {
        rep(i,0,nown-1)if(i<r[i])swap(u[i],u[r[i]]);
        for(int i=1;i<nown;i<<=1)
        {
            cd wn(cos(pi/i),sin(f*pi/i)),x,y;
            for(int j=0;j<nown;j+=(i<<1))
            {
                cd w(1,0);
                rep(k,0,i-1)
                    x=u[j+k],y=w*u[i+j+k],u[j+k]=x+y,u[i+j+k]=x-y,w*=wn;
            }
        }
        if(f==-1.0){rep(i,0,nown-1)u[i]/=nown;}
    }
    int main()
    {
        scanf("%d%d%s%s",&l1,&l2,s1,s2);
        reverse(s1,s1+l1);
        rep(i,0,l1-1)a[i]=s1[i]=='*'?0:(s1[i]-'a'+1);
        rep(i,0,l2-1)b[i]=s2[i]=='*'?0:(s2[i]-'a'+1);
        getlen(max(l1,l2)*4);
        rep(i,0,nown-1)A[i]=a[i]*a[i]*a[i],B[i]=b[i];
        dft(A,1),dft(B,1);
        rep(i,0,nown-1)c[i]=A[i]*B[i];
        rep(i,0,nown-1)A[i]=a[i],B[i]=b[i]*b[i]*b[i];
        dft(A,1),dft(B,1);
        rep(i,0,nown-1)c[i]+=A[i]*B[i];
        rep(i,0,nown-1)A[i]=a[i]*a[i],B[i]=b[i]*b[i];
        dft(A,1),dft(B,1);
        rep(i,0,nown-1)c[i]-=2.0*A[i]*B[i];
        dft(c,-1);
        rep(i,l1-1,l2-1)if(((int)(c[i].real()+0.5))==0)ans[++num]=i-l1+2;
        write(num);puts("");
        rep(i,1,num)write(ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/xzyf/p/11598961.html

[Link 1]: https://www.cnblogs.com/xiao-ju-ruo-xjr/p/9149792.html