题面

传送门

bzoj上的这两题是一样的......

正文

我看到这道题，第一想法是跑魔改过的KMP，然后很快发现不可行

于是想换个角度思考

其实，本题最大的问题就在于通配符的存在：它可以匹配任意一个字符

那么我们考虑一个办法：令两个字符匹配成为“抵消”，那么数学上的抵消会让我们想到什么呢？

没错，0

我们令所有的通配符为0，让匹配变成两个字符相乘，那么乘出来零就“抵消”了

想到这里以后，一个非常自然的想法就是令所有的普通字符匹配也变成乘积为0的，但是这显然不可行，因为这个方法一定会导致不同字符乘起来也等于0（我们有26个字幕呢！！！）

现在这个问题就比较烦了，但是我们依然不能放弃希望

考虑0，除了作为非正非负数以外，它还有什么特性？

没错，零是一个整数

整数？整数......我们只要让匹配成功的字符，乘起来等于整数不就好了！

接下来的思路就比较清晰了：我们令第i种字母，在文本串（B串）中的值为i，在模式串（A串）中为$\frac 1i$，这样如果A串和B串某一位匹配，就会得到一个1

但是还有一个问题：如果遇到$4\ast\frac 12=2$这样的怎么办？

好说，我们令i等于10000+i就好了

我们把模式串A翻过来，然后让它与B串做FFT乘法

得到的第i位如果是整数，那么意味着从第i-n位开始的、长度为n的B串子串能与A匹配(n<i<=n*\2)

精度记得卡一卡，卡到1e-6就差不多了

貌似有的OJ只需要加1000？反正这是个玄学做法，总是能卡掉的吧......

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

inline int read(){

    int re=0,flag=1;char ch=getchar();

    while(ch>'9'||ch<'0'){

        if(ch=='-') flag=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

    return re*flag;

}

struct complex{

    double x,y;

    complex(double xx=0,double yy=0){x=xx;y=yy;}

    complex operator +(const complex &b){return complex(x+b.x,y+b.y);}

    complex operator -(const complex &b){return complex(x-b.x,y-b.y);}

    complex operator *(const complex &b){return complex(x*b.x-y*b.y,x*b.y+y*b.x);}

}A[2000010],B[2000010];

const double pi=acos(-1.0);

int n,m,limit=1,cnt=0,r[2000010];

void fft(complex *a,double type){

    int i,j,k,mid;complex x,y,w,wn;

    for(i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);

    for(mid=1;mid<limit;mid<<=1){

        wn=complex(cos(pi/mid),type*sin(pi/mid));

        for(j=0;j<limit;j+=(mid<<1)){

            w=complex(1,0);

            for(k=0;k<mid;k++,w=w*wn){

                x=a[j+k];y=w*a[j+k+mid];

                a[j+k]=x+y;a[j+k+mid]=x-y;

            }

        }

    }

}

vector<int>ans;

char s[300010];

int main(){

    m=read();n=read();int i,tmp;

    scanf("%s",s);

    for(i=0;i<m;i++){

        if(s[i]=='*') B[m-i].x=0;

        else B[m-i].x=(1.0/(10001.0+double(s[i]-'a')));

    }

    scanf("%s",s);

    for(i=0;i<n;i++){

        if(s[i]=='*') A[i+1].x=0;

        else A[i+1].x=(10001.0+double(s[i]-'a'));

    }

    while(limit<=(n+m)) limit<<=1,cnt++;

    for(i=0;i<limit;i++) r[i]=((r[i>>1]>>1)|((i&1)<<(cnt-1)));

    fft(A,1);fft(B,1);

    for(i=0;i<=limit;i++) A[i]=A[i]*B[i];

    fft(A,-1);

    for(i=m+1;i<=n+1;i++){

        A[i].x/=(double)limit;tmp=(int)(A[i].x+0.5);

        if(abs(A[i].x-(double(tmp)))<=1e-6) ans.push_back(i-m);

    }

    printf("%d\n",ans.size());

    for(i=0;i<ans.size();i++) printf("%d ",ans[i]);

}

巴特西

[bzoj4259][bzoj4503] 残缺的字符串 [FFT]

题面

传送门

正文

没错，零是一个整数

最新文章

热门文章