给定母串$S$和模式串$T$，字符集大小为$4$，给定$k$，一个字符$c$在位置$i$被匹配当且仅当$[i-k,i+k]$中存在字符与$c$相同。问有多少个点满足模式串从这个点平铺开来所有字母可以被匹配
一道裸题搞得我天昏地暗。。都怪毛爷爷题解写的很藐视低智商
首先对于每种字符分开处理。对于母串把字符$c$以及它可以够到的位置($[i-k,i+k]$)全部赋值为$1$
把模式串的字符为$c$的位置也赋值为$1$
没有赋值的地方值就是$0$了
设字符的值为$p_i$，母串的值为$q_i$
字符$c$对点$i$的贡献即为$val_i=\sum_{j=1}^{\mid T \mid }p_jq_{i+j-1}$
如果反转一个数组(比如$q$)，则可以构造卷积的形式:
那么反转$q$就得到了$val_i=\sum_{j=1}^{\mid T \mid }p_jq_{\mid S \mid +1-i-j}$
那个$\mid T\mid $可以用$\mid S \mid +1 -i$代掉，令它为$n$
因为$val_i$的位置不重要，所以把$i$直接变成$n$(如果要深究的话其实就是反转了)
于是得到了$val_n=\sum_{j=1}^n p_i q_{n-i}$，$FFT$得到
如果$4$种字符对$i$的贡献和为$\mid T \mid $那么在$i$处匹配了
因为$4$个操作是完全相同的，所以不管下标怎么变$4$个字符对于相同点的代价会累到一个相同位置，这也是之前说下标不重要的原因
这题样例都卡精度搞得我欲仙欲死
一开始敲没有考虑$FFT$时的长度应该大于$\mid S \mid +\mid T \mid$，调了超久，这个坑很容易跳的样子
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<complex>
using namespace std;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
const int M=1e6+5;
typedef double db;
typedef complex<db> comp;
const db twpi=3.14159265358*2;
char S[M],T[M];
int n,m,sum[M],k,w,rev[M];
comp p[M],q[M],res[4][M];
inline void DFT(comp *res,int n,int sg){
for(int i=0;i<n;++i)
if(rev[i]>i)swap(res[i],res[rev[i]]);
for(int s=2;s<=n;s<<=1){
comp wm(cos(twpi/s),sin(twpi/s)*sg);
for(int i=0;i<n;i+=s){
comp w(1,0);
for(int j=0;j<s>>1;++j,w*=wm){
comp a=res[j+i],b=res[j+i+(s>>1)];
res[i+j]=a+b*w,res[i+j+(s>>1)]=a-b*w;
}
}
}
}
inline void work(comp res[],char c){
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+(S[i]==c);
for(int i=1;i<=w;++i)
p[i-1]=T[i]==c;
for(int i=1;i<=w;++i)
if(i<=n)q[n-i]=(bool){sum[i]-sum[max(0,i-k-1)]}|(bool){sum[min(n,i+k)]-sum[i-1]};
else q[i-1]=0;
DFT(p,w,1),DFT(q,w,1);
for(int i=0;i<w;++i)
res[i]=p[i]*q[i];
DFT(res,w,-1);
for(int i=0;i<w;++i)res[i]/=w;
}
inline void pret(){
int s=0;
for(w=1;w<=n;w<<=1,++s);
++s,w<<=1;
for(int i=1;i<w;++i)
rev[i]=rev[i>>1]>>1|(i&1)<<s-1;
}
int main(){
cin>>n>>m>>k;
scanf("%s %s",S+1,T+1);
pret();
work(res[0],'A'),work(res[1],'T');
work(res[2],'C'),work(res[3],'G');
int ans=0;
for(int i=0;i<w;++i){
int s=0;
for(int j=0;j<=3;++j)
s+=(int){res[j][i].real()+0.5};
ans+=s==m;
}
cout<<ans<<endl;
return 0;
}