zcmimi's blog
avatar
zc
2020-07-25 23:00:00
  • 本文总阅读量
查看原题

点击跳转

设通配符的数值为0,定义匹配函数C(x,y)=[A(x)-B(y)]^2A(x)B(y),那么\displaystyle P(x)=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)

按照套路,翻转A串得到S串:

\displaystyle \begin{aligned} P(x) &=\sum_{i=0}^{m-1}[A(i)-B(x-m+i+1)]^2A(i)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}[S(m-i+1)-B(x-m+i+1)]^2S(m-i+1)B(x-m+i+1)\\ &=\sum_{i=0}^{m-1}S(m-i+1)^3B(x-m+i+1)+\\ &\quad\sum_{i=0}^{m-1}B(x-m+i+1)^3S(m-i+1)-\\ &\quad2\sum_{i=0}^{m-1}S(m-i+1)^2B(x-m+i+1)^2 \end{aligned}

写为卷积形式:

\displaystyle P(x)=\sum_{i+j=x}S(i)^3B(j)+S(i)B(j)^3-2S(i)^2B(j)^2

#include<bits/stdc++.h>
const int N=1100011;
int n,m,L,r[N],l,a[N],b[N],ans[N],tt;
char s1[N],s2[N];
typedef double db;
const db Pi=acos(-1);
struct cp{db r,i;cp(db R=0,db I=0){r=R,i=I;}}A[N],B[N],AS[N];
cp operator+(cp a,cp b){return cp(a.r+b.r,a.i+b.i);}
cp operator-(cp a,cp b){return cp(a.r-b.r,a.i-b.i);}
cp operator*(cp a,cp b){return cp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}
void swap(cp&x,cp&y){cp t=x;x=y;y=t;}
void fft(cp*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        cp Wn(cos(Pi/len),typ*sin(Pi/len));
        for(int i=0;i<L;i+=len<<1){
            cp w(1,0);
            for(int k=0;k<len;++k){
                cp t=w*A[i+k+len];
                A[i+k+len]=A[i+k]-t;
                A[i+k]=A[i+k]+t;
                w=w*Wn;
            }
        }
    }
    if(~typ)return;
    for(int i=0;i<L;++i)
        A[i].r/=L,A[i].i/=L;
}
int main(){
    scanf("%d%d%s%s",&m,&n,s1,s2);
    std::reverse(s1,s1+m);
    for(int i=0;i<m;++i)a[i]=s1[i]=='*'?0:s1[i]-'a'+1;
    for(int i=0;i<n;++i)b[i]=s2[i]=='*'?0:s2[i]-'a'+1;

    for(L=1,l=0;L<n+n;L<<=1,++l);
    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));

    for(int i=0;i<L;++i)
        A[i]=cp(a[i]*a[i]*a[i],0),
        B[i]=cp(b[i],0);
    fft(A,1),fft(B,1);
    for(int i=0;i<L;++i)AS[i]=AS[i]+A[i]*B[i];

    for(int i=0;i<L;++i)
        A[i]=cp(a[i],0),
        B[i]=cp(b[i]*b[i]*b[i],0);
    fft(A,1),fft(B,1);
    for(int i=0;i<L;++i)AS[i]=AS[i]+A[i]*B[i];

    for(int i=0;i<L;++i)
        A[i]=cp(a[i]*a[i],0),
        B[i]=cp(b[i]*b[i],0);
    fft(A,1),fft(B,1);
    for(int i=0;i<L;++i)AS[i]=AS[i]-A[i]*B[i]*cp(2,0);

    fft(AS,-1);
    for(int i=m-1;i<n;i++)
        if(fabs(AS[i].r)<0.5)ans[++tt]=i-m+2;
    printf("%d\n",tt);
    for(int i=1;i<=tt;++i)printf("%d ",ans[i]);
}
LG 4173 残缺的字符串
comment评论
Search
search