BZOJ 4259 残缺的字符串

思路

同样是FFT进行字符串匹配

只不过两个都有通配符

匹配函数再乘一个\(A_i\)即可
代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#define int long long

using namespace std;

const int MAXN = 1200000;

const int MOD = 998244353;

const int G = 3;

const int invG = 332748118;

int rev[MAXN];

void cal_rev(int n,int lim){

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

        rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));

}

int pow(int a,int b){

    int ans=1;

    while(b){

        if(b&1)

            ans=(1LL*ans*a)%MOD;

        a=(1LL*a*a)%MOD;

        b>>=1;

    }

    return ans;

}

void NTT(int *a,int opt,int n,int lim){

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

        if(i<rev[i])

            swap(a[i],a[rev[i]]);

    for(int i=2;i<=n;i<<=1){

        int len=i/2,tmp=pow((opt)?G:invG,(MOD-1)/i);

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

            int arr=1;

            for(int k=j;k<j+len;k++){

                int t=(1LL*a[k+len]*arr)%MOD;

                a[k+len]=(a[k]-t+MOD)%MOD;

                a[k]=(a[k]+t)%MOD;

                arr=(1LL*arr*tmp)%MOD;

            }

        }

    }

    if(!opt){

        int invN = pow(n,MOD-2);

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

            a[i]=(1LL*a[i]*invN)%MOD;

    }

}

int n,m,s[MAXN],t[MAXN],a[MAXN],b[MAXN],c[MAXN],ans[MAXN],cnt;

char S[MAXN];

signed main(){

    freopen("test.in","r",stdin);

    freopen("test.out","w",stdout);

    scanf("%lld %lld",&m,&n);

    scanf("%s",S);

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

        t[i]=(S[i]=='*')?0:S[i]-'a'+1;

    reverse(t,t+m);

    scanf("%s",S);

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

        s[i]=(S[i]=='*')?0:S[i]-'a'+1;

    int midlen=1,midlim=0;

    while(midlen<(n+m))

        midlen<<=1,midlim++;

    cal_rev(midlen,midlim);

    for(int i=0;i<midlen;i++)

        a[i]=(s[i]*s[i]*s[i])%MOD,b[i]=t[i];

    NTT(a,1,midlen,midlim);

    NTT(b,1,midlen,midlim);

    for(int i=0;i<midlen;i++)

        c[i]=(a[i]*b[i])%MOD;

    for(int i=0;i<midlen;i++)

        a[i]=(2*s[i]*s[i])%MOD,b[i]=(t[i]*t[i])%MOD;

    NTT(a,1,midlen,midlim);

    NTT(b,1,midlen,midlim);

    for(int i=0;i<midlen;i++)

        c[i]=(c[i]-a[i]*b[i]+MOD)%MOD;

    for(int i=0;i<midlen;i++)

        a[i]=s[i],b[i]=(t[i]*t[i]*t[i])%MOD;

    NTT(a,1,midlen,midlim);

    NTT(b,1,midlen,midlim);

    for(int i=0;i<midlen;i++)

        c[i]=(c[i]+a[i]*b[i])%MOD;

    NTT(c,0,midlen,midlim);

    // for(int i=0;i<midlen;i++)

    //     printf("!%lld\n",c[i]);

    for(int i=m-1;i<n;i++)

        if(!c[i])

            ans[++cnt]=i-m+1;

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

    for(int i=1;i<=cnt;i++)

        printf("%lld ",ans[i]+1);

    return 0;

}
巴特西

BZOJ 4259 残缺的字符串

思路

代码

最新文章

热门文章
