【做题记录】CF528D Fuzzy Search

· · 题解

题目：

有一个长度为 n 的串 S，以及长度为 m 的串 T。

现给定一个数 k ，我们说 T 在 S 的位置 i 匹配上，当且仅当对于每一个 1\le a\le m ，都有一个位置 1\le b\le n 满足 |(i+a-1)-b|\le k ，且 S_b=T_a 。

请回答 T 在 S 中匹配上了多少个不同的位置。

n,m,k\le2*10^5

题解：

记 p_{i,ch} 表示位置 i 上放上字符 ch 是否合法。p_{i,ch}=1 当且仅当存在 s_j=ch 且 |i-j|\leq k。

求 p_{i,ch} ，对于 s_i=c 将 p_{i-k,ch},p_{i-k+1,ch},\dots,p_{i+k-1,ch},p_{i+k,ch} 设为 1，差分就行了。

设 f_i 表示以 i 开头的长度为 |T| 字符串能与 T 成功匹配多少位。

f_i=\sum\limits_{j=1}^{|T|}p_{i+j-1,t_j}

枚举每个字符 ch\in\{\text{ACTG}\}，设 flag_j 表示 T_j 是否等于 ch。那么字符 ch 给 f_i 带来的贡献就是

f_i=\sum\limits_{j=1}^{|T|}p_{i+j-1,ch}\times flag_j

那么原式即为

ans=\sum\limits_{x-y=i}f_xflag_y

将 S 翻转一下，得

ans=\sum\limits_{x+y=i}f_xflag_y

用 \text{FFT} 一卷即可。