CF528D Fuzzy Search

$k=0k=0$k=0时

题目保证只有四个字母$"ATGC""ATGC"$"ATGC"，暗示我们可以先分成4种情况处理，最后加起来。

比如说文本串$S="TAATGCA"S="TAATGCA"$S="TAATGCA"和模板串$T="AATGC"T="AATGC"$T="AATGC"

先处理$AA$A的情况：

$S="\#AA\#\#\#A"S="\backslash \#AA\backslash \#\backslash \#\backslash \#A"$S="#AA###A"

$T="AA\#\#\#"T="AA\backslash \#\backslash \#\backslash \#"$T="AA###"

以$S\left(5\right)S(5)$S(5)（下标以0开始）结尾的长度为5的子串和模板串匹配的长度为2

同理，处理$TT$T的情况，以$S\left(5\right)S(5)$S(5)结尾的长度为5的子串和模板串匹配的长度为1

处理$CC$C的情况，以$S\left(5\right)S(5)$S(5)结尾的长度为5的子串和模板串匹配的长度为1

处理$GG$G的情况，以$S\left(5\right)S(5)$S(5)结尾的长度为5的子串和模板串匹配的长度为1

加起来后可知，以$S\left(5\right)S(5)$S(5)结尾的长度为5的子串和模板串匹配的长度为5，即以$S\left(5\right)S(5)$S(5)结尾的长度为5的子串和模板串完全匹配

$k>0k>0$k>0时，可以理解为将文本串中的字母$CC$C（当前在处理字母$cc$c的情况）往两边扩散$kk$k个距离。

比如$k=1k=1$k=1，此时先处理$AA$A的情况：

$S="AAAA\#\#A"S="AAAA\backslash \#\backslash \#A"$S="AAAA##A"

$T="AA\#\#\#"T="AA\backslash \#\backslash \#\backslash \#"$T="AA###"

以$S\left(5\right)S(5)$S(5)（下标以0开始）结尾的长度为5的子串和模板串匹配的长度为2

当前处理字符$cc$c时，接下来就是构造多项式$f={\sum }_{i=0}^{n-1}\left[S\right[i]={=}^{\prime }{c}^{\prime }]\ast x^{i}f=\backslash sum\_\{i=0\}^\{n-1\}[S[i]==\text{'}c\text{'}]*x^i$f=∑i=0n−1​[S[i]==′c′]∗xi，多项式$g={\sum }_{i=0}^{m-1}\left[T\right[m-1-i]={=}^{\prime }{c}^{\prime }]\ast x^{i}g=\backslash sum\_\{i=0\}^\{m-1\}[T[m-1-i]==\text{'}c\text{'}]*x^i$g=∑i=0m−1​[T[m−1−i]==′c′]∗xi，然后$a=f\ast sa=f*s$a=f∗s，a(d)=∑i+j=d​[S[i]==′c′&&T[m−1−j]==′c′]xd就表示以$S\left(i\right)S(i)$S(i)结尾的长度为$m-1m-1$m−1的子串和模板串匹配的长度。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=(1<<19)+7,mod=998244353;
inline int qpow(int x,int y) {
	int res(1);
	while(y) {
		if(y&1) res=1LL*res*x%mod;
		x=1LL*x*x%mod;
		y>>=1;
	}
	return res;
}
int r[maxn];
inline void ntt(int *x,int lim,int opt) {
	int i,j,k,m,gn,g,tmp;
	for(i=0; i<lim; ++i)
		if(i<r[i]) swap(x[i],x[r[i]]);
	for(m=2; m<=lim; m<<=1) {
		k=m>>1;
		gn=qpow(3,(mod-1)/m);
		for(i=0; i<lim; i+=m) {
			g=1;
			for(j=0; j<k; ++j,g=1LL*g*gn%mod) {
				tmp=1LL*x[i+j+k]*g%mod;
				x[i+j+k]=(x[i+j]-tmp+mod)%mod;
				x[i+j]=(x[i+j]+tmp)%mod;
			}
		}
	}
	if(opt==-1) {
		reverse(x+1,x+lim);
		int inv=qpow(lim,mod-2);
		for(i=0; i<lim; ++i) x[i]=1LL*x[i]*inv%mod;
	}
}
int A[maxn],B[maxn],cnt[maxn],n,m,k,lim(1);
char a[maxn],b[maxn];
void solve(char c) {
	for(int i=0;i<lim;++i) A[i]=B[i]=0;
	for(int i=0,last=-1e9;i<n;++i) {
		if(a[i]==c) last=i;
		if(i-last<=k) A[i]=1;
	}
	for(int i=n-1,last=1e9;~i;--i) {
		if(a[i]==c) last=i;
		if(last-i<=k) A[i]=1;
	}
	for(int i=0;i<m;++i) B[i]=(b[m-1-i]==c);
	ntt(A,lim,1),ntt(B,lim,1);
	for(int i=0; i<lim; ++i) A[i]=1LL*A[i]*B[i]%mod;
	ntt(A,lim,-1);
	for(int i=0;i<lim;++i) cnt[i]+=A[i];
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s%s",a,b);
	while(lim<(n<<1)) lim<<=1;
	for(int i=0; i<lim; ++i) r[i]=(i&1)*(lim>>1)+(r[i>>1] >> 1);
	for(int i=0;i<4;++i) solve("ATGC"[i]);
	int ans(0);
	for(int i=m-1;i<lim;++i) ans+=(cnt[i]==m);
	cout<<ans<<'\n';
	return 0;
}