即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

[BZOJ4259]残缺的字符串(FFT)

编程语言 Clove_unique 8℃ 0评论
本文目录
[隐藏]

1.题目描述

传送门

题目大意:给出一个模板串和一个母串,问模板串在母串中出现过几次。带通配符。

2.题解

这道题和两个串那道题是差不多的。。


令F(i)表示将模板串的最后一个怼到母串的第i个是否能匹配,0表示能匹配,非0表示不能匹配。然后设两个函数f(i)=(t(i)=‘ * ’)?0:t(i),g(i)=(s(i)=‘ * ’)?0:s(i)


将模板串倒置了之后显然F(i)=j=0S1f(ij)g(j)(f(ij)g(j))2=f(ij)3g(j)2f(ij)2g(j)2+f(ij)g(j)3是一个卷积的形式


这样做三遍FFT求出F(i)就行了

3.代码

#include
#include
#include
#include
#include
using namespace std;
#define N 2000005

const double pi=acos(-1.0);
struct complex
{
    double x,y;
    complex(double X=0,double Y=0)
    {
        x=X,y=Y;
    }
}a[N],b[N];
complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int S,T,n,m,L,R[N],ans[N];
long long F[N];
char s[N],t[N];
double f[N],g[N];

void FFT(complex a[N],int opt)
{
    for (int i=0;iif (ifor (int k=1;k1)
    {
        complex wn=complex(cos(pi/k),opt*sin(pi/k));
        for (int i=0;i1))
        {
            complex w=complex(1,0);
            for (int j=0;jcomplex x=a[i+j],y=w*a[i+j+k];
                a[i+j]=x+y,a[i+j+k]=x-y;
            }
        }
    }
}
void calc(int opt)
{
    FFT(a,1);FFT(b,1);
    for (int i=0;i<=n;++i) a[i]=a[i]*b[i];
    FFT(a,-1);
    for (int i=0;ilong long)(a[i].x/n+0.5)*opt;
}
int main()
{
    scanf("%d%d",&S,&T);
    scanf("%s%s",s,t);
    for (int i=0;i2;++i) swap(s[i],s[S-i-1]);

    for (int i=0;i'*')?0:(t[i]-'a'+1.0);
    for (int i=0;i'*')?0:(s[i]-'a'+1.0);

    m=S+T-2;
    for (n=1;n<=m;n<<=1) ++L;
    for (int i=0;i>1]>>1)|((i&1)<<(L-1));

    for (int i=0;i<=n;++i) a[i]=complex(0,0),b[i]=complex(0,0);
    for (int i=0;ifor (int i=0;i1);
    for (int i=0;i<=n;++i) a[i]=complex(0,0),b[i]=complex(0,0);
    for (int i=0;ifor (int i=0;i2);
    for (int i=0;i<=n;++i) a[i]=complex(0,0),b[i]=complex(0,0);
    for (int i=0;ifor (int i=0;i1);

    for (int i=S-1;iif (!F[i]) ans[++ans[0]]=i-S+2;
    printf("%d\n",ans[0]);
    for (int i=1;i<=ans[0];++i) printf("%d%c",ans[i]," \n"[i==ans[0]]);
}

转载请注明:CodingBlog » [BZOJ4259]残缺的字符串(FFT)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情