题目概述

CF528D

解题报告

奇怪的字符串匹配，并且字符集很小，考虑卷积。

对于字符 $ch$ ，如果 $S$ 的 $i$ 位置是 $ch$ ，说明 $[i-K,i+K]$ 这些位置都可以匹配。

令 $S$ 中可以匹配的位置 $i$ 的生成函数 $F(x)=\sum x^i$ ，$T$ 中可以匹配的位置 $j$ 的生成函数 $G(x)=\sum x^{-j}$ 。

则 $F(x)G(x)$ 就可以得出匹配的位置，最后判断 $S$ 所有位置的累计匹配次数是不是 $m$ 即可。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=1<<19,MOD=998244353;

int n,m,K,ans,sum[maxn+5],cnt[maxn+5];
char s[maxn+5],t[maxn+5];
int T,wn[maxt+5],F[maxt+5],G[maxt+5];

inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
inline int MUL(int x,int y) {return (LL)x*y%MOD;}
int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
__attribute__((constructor)) void NTTPre(){
    int x=Pow(3,(MOD-1)/maxt);
    wn[maxt>>1]=1;
    for (int i=(maxt>>1)+1;i<maxt;i++) wn[i]=MUL(wn[i-1],x);
    for (int i=(maxt>>1)-1;i;i--) wn[i]=wn[i<<1];
}
void NTT(int *a,int n,int f){
    if (f>0){
        for (int k=n>>1;k;k>>=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=a[i+j+k];
                    a[i+j+k]=MUL(x+MOD-y,wn[k+j]);
                    a[i+j]=ADD(x,y);
                }
    } else {
        for (int k=1;k<n;k<<=1)
            for (int i=0;i<n;i+=k<<1)
                for (int j=0;j<k;j++){
                    int x=a[i+j],y=MUL(a[i+j+k],wn[k+j]);
                    a[i+j+k]=ADD(x,MOD-y);
                    a[i+j]=ADD(x,y);
                }
        for (int i=0,INV=MOD-(MOD-1)/n;i<n;i++) a[i]=MUL(a[i],INV);
        reverse(a+1,a+n);
    }
}
void Solve(char ch){
    for (int i=0;i<T;i++) F[i]=G[i]=0;
    for (int i=0;i<=n;i++) sum[i]=0;
    for (int i=0;i<=n;i++)
        if (s[i]==ch){
            int L=max(i-K,0),R=min(i+K,n);
            sum[L]++;sum[R+1]--;
        }
    for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
    for (int i=0;i<=n;i++) if (sum[i]) F[i]=1;
    for (int i=0;i<=m;i++) if (t[i]==ch) G[m-i]=1;
    NTT(F,T,1);NTT(G,T,1);
    for (int i=0;i<T;i++) F[i]=MUL(F[i],G[i]);
    NTT(F,T,-1);
    for (int i=0;i<=n-m;i++) cnt[i]+=F[i+m];
}
int main(){
    scanf("%d%d%d%s%s",&n,&m,&K,s,t);n--;m--;
    for (T=1;T<=n+m;T<<=1);
    Solve('A');Solve('T');Solve('G');Solve('C');
    for (int i=0;i<=n-m;i++) if (cnt[i]==m+1) ans++;
    printf("%d\n",ans);
    return 0;
}