BZOJ4259: 残缺的字符串 & BZOJ4503: 两个串

2022-09-18 12:14:29

【传送门：BZOJ4259&BZOJ4503】

简要题意：

　　给出两个字符串，第一个串长度为m，第二个串长度为n，字符串中如果有*字符，则代表当前位置可以匹配任何字符

　　求出第一个字符串在第二个字串中出现的次数，及出现的位置开头在第二个字符串的位置（从小到大输出）

题解：

　　FFT，通配符匹配

　　两道题几乎没区别

　　对于两个串长度为i，它们的相似程度为$\sum_{j=0}^{i-1}(A[j]-B[j])^2$(A[j]!='*'&&B[j]!='*')

　　把*设为0，则得到$\sum_{j=0}^{i-1}(A[j]-B[j])^2A[j]B[j]$

　　显然只有当$\sum_{j=0}^{i-1}(A[j]-B[j])^2A[j]B[j]$为0时，A串和B串才能完全匹配

　　那么对于这道题而言，设f(i)为以B的i位置为结尾的长度为n的子串与A串的相似程度

　　先将n--,m--（方便写公式），然后在A后面补0

　　显然$f(i)=\sum_{j=0}^{m}(A[j]-B[i-m+j])^2A[j]B[i-m+j]$

　　我们把A数组翻转，就会得到$f(i)=\sum_{j=0}^{i}(A[j]-B[i-j])^2A[j]B[i-j]$

　　然后把这个式子拆开就得到$f(i)=\sum_{j=0}^{i}A[j]^3B[i-j]-2*\sum_{j=0}^{i}A[j]^2B[i-j]^2+\sum_{j=0}^{i}A[j]*B[i-j]^3$

　　皆大欢喜，直接三次FFT分别求就可以了

参考代码（一）：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const double PI=acos(-1.0);

struct Complex

{

    double r,i;

    Complex(){}

    Complex(double _r,double _i){r=_r;i=_i;}

    friend Complex operator + (const Complex &x,const Complex &y){return Complex(x.r+y.r,x.i+y.i);}

    friend Complex operator - (const Complex &x,const Complex &y){return Complex(x.r-y.r,x.i-y.i);}

    friend Complex operator * (const Complex &x,const Complex &y){return Complex(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}

}a[],b[];

int R[];

void fft(Complex *y,int len,int on)

{

    for(int i=;i<len;i++) if(i<R[i]) swap(y[i],y[R[i]]);

    for(int i=;i<len;i<<=)

    {

        Complex wn(cos(PI/i),sin(on*PI/i));

        for(int j=;j<len;j+=(i<<))

        {

            Complex w(,);

            for(int k=;k<i;k++,w=w*wn)

            {

                Complex u=y[j+k];

                Complex v=w*y[j+k+i];

                y[j+k]=u+v;

                y[j+k+i]=u-v;

            }

        }

    }

    if(on==-) for(int i=;i<=len;i++) y[i].r/=len;

}

void calc(int n,int m)

{

    int L=;m+=n;

    for(n=;n<=m;n<<=) L++;

    memset(R,,sizeof(R));

    for(int i=;i<n;i++) R[i]=(R[i>>]>>)|(i&)<<(L-);

    fft(a,n,);fft(b,n,);

    for(int i=;i<=n;i++) a[i]=a[i]*b[i];

    fft(a,n,-);

}

char s1[],s2[];

int A[],B[];

int q[];

double f[];

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);n--;m--;

    scanf("%s%s",s1,s2);

    for(int i=;i<=n;i++)

    {

        if(s1[n-i]=='*') A[i]=;

        else A[i]=s1[n-i]-'a'+;

    }

    for(int i=;i<=m;i++)

    {

        if(s2[i]=='*') B[i]=;

        else B[i]=s2[i]-'a'+;

    }

    memset(f,,sizeof(f));

    for(int i=;i<=n;i++) a[i].r=A[i]*A[i]*A[i];

    for(int i=;i<=m;i++) b[i].r=B[i];

    calc(n,m);

    for(int i=;i<=m;i++) f[i]+=a[i].r;

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    for(int i=;i<=n;i++) a[i].r=A[i]*A[i];

    for(int i=;i<=m;i++) b[i].r=B[i]*B[i];

    calc(n,m);

    for(int i=;i<=m;i++) f[i]-=2.0*a[i].r;

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    for(int i=;i<=n;i++) a[i].r=A[i];

    for(int i=;i<=m;i++) b[i].r=B[i]*B[i]*B[i];

    calc(n,m);

    for(int i=;i<=m;i++) f[i]+=a[i].r;

    int cnt=;

    for(int i=n;i<=m;i++) if(f[i]<0.5) q[++cnt]=i-n;

    printf("%d\n",cnt);

    if(cnt>)

    {

        for(int i=;i<cnt;i++) printf("%d ",q[i]+);

        printf("%d\n",q[cnt]+);

    }

    return ;

}

参考代码（二）：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const double PI=acos(-1.0);

struct Complex

{

    double r,i;

    Complex(){}

    Complex(double _r,double _i){r=_r;i=_i;}

    friend Complex operator + (const Complex &x,const Complex &y){return Complex(x.r+y.r,x.i+y.i);}

    friend Complex operator - (const Complex &x,const Complex &y){return Complex(x.r-y.r,x.i-y.i);}

    friend Complex operator * (const Complex &x,const Complex &y){return Complex(x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r);}

}a[],b[];

int R[];

void fft(Complex *y,int len,int on)

{

    for(int i=;i<len;i++) if(i<R[i]) swap(y[i],y[R[i]]);

    for(int i=;i<len;i<<=)

    {

        Complex wn(cos(PI/i),sin(on*PI/i));

        for(int j=;j<len;j+=(i<<))

        {

            Complex w(,);

            for(int k=;k<i;k++,w=w*wn)

            {

                Complex u=y[j+k];

                Complex v=w*y[j+k+i];

                y[j+k]=u+v;

                y[j+k+i]=u-v;

            }

        }

    }

    if(on==-) for(int i=;i<=len;i++) y[i].r/=len;

}

void calc(int n,int m)

{

    int L=;m+=n;

    for(n=;n<=m;n<<=) L++;

    memset(R,,sizeof(R));

    for(int i=;i<n;i++) R[i]=(R[i>>]>>)|(i&)<<(L-);

    fft(a,n,);fft(b,n,);

    for(int i=;i<=n;i++) a[i]=a[i]*b[i];

    fft(a,n,-);

}

char s1[],s2[];

int A[],B[];

int q[];

double f[];

int main()

{

    int m,n;

    scanf("%s%s",s1,s2);

    m=strlen(s1);n=strlen(s2);

    m--;n--;

    for(int i=;i<=m;i++) B[i]=s1[i]-'a'+;

    for(int i=;i<=n;i++)

    {

        if(s2[n-i]=='?') A[i]=;

        else A[i]=s2[n-i]-'a'+;

    }

    memset(f,,sizeof(f));

    for(int i=;i<=n;i++) a[i].r=A[i]*A[i]*A[i];

    for(int i=;i<=m;i++) b[i].r=B[i];

    calc(n,m);

    for(int i=;i<=m;i++) f[i]+=a[i].r;

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    for(int i=;i<=n;i++) a[i].r=A[i]*A[i];

    for(int i=;i<=m;i++) b[i].r=B[i]*B[i];

    calc(n,m);

    for(int i=;i<=m;i++) f[i]-=2.0*a[i].r;

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    for(int i=;i<=n;i++) a[i].r=A[i];

    for(int i=;i<=m;i++) b[i].r=B[i]*B[i]*B[i];

    calc(n,m);

    for(int i=;i<=m;i++) f[i]+=a[i].r;

    int cnt=;

    for(int i=n;i<=m;i++) if(f[i]<0.5) q[++cnt]=i-n;

    printf("%d\n",cnt);

    if(cnt>) for(int i=;i<=cnt;i++) printf("%d\n",q[i]);

    return ;

}
上一篇：layui常见问题记录


下一篇：BZOJ4259 残缺的字符串 多项式 FFT