CF528D Fuzzy Search 做题记录

给出一个门限值 $k$ 和两个只包含 $\texttt{AGCT}$ 四种字符的基因串 $S$ 和 $T$。现在你要找出在下列规则中 $T$ 在 $S$ 中出现了几次。

$T$ 在 $S$ 的第 $i$ 个位置中出现，当且仅当把 $T$ 的首字符和 $S$ 的第 $i$ 个字符对齐后，$T$ 中的每一个字符能够在 $S$ 中找到一个位置偏差不超过 $k$ 的相同字符。

即对于所有的 $j \in[1,|T|]$，都存在一个 $p \in [1,|S|]$ 使得 $|(i+j-1)-p| \leq k$ 且 $S_p=T_j$ 。

例如 $k=1$ 时，$\texttt{ACAT}$ 出现在 $\texttt{AGCAATTCAT}$ 的 $2$ 号， $3$ 号和 $6$ 号位置。 (编号从 $1$ 开始。)

考虑设 $A,C,G,T$ 是四个 $01$ 序列，表示四种字母是否能在 $S$ 的某一位上匹配；设 $A_*,C_*,G_*,T_*$ 是四个 $01$ 序列表示 $T$ 的某一位上是否某种字母。

例如样例中：

$A=\{1,1,1,1,1,1,0,1,1,1\}$

$C=\{0,1,1,1,0,0,1,1,1,0\}$

$G=\{1,1,1,0,0,0,0,0,0,0\}$

$T=\{0,0,0,0,1,1,1,1,1,1\}$

$A_*=\{1,0,1,0\}$

$C_*=\{0,1,0,0\}$

$G_*=\{0,0,0,0\}$

$T_*=\{0,0,0,1\}$

若某个位置 $S$ 和 $T$ 对应的序列同时为 $1$，那么贡献 $1$，否则贡献 $0$，也就是做乘法。那么匹配当且仅当四种字符的贡献和是串长。

考虑怎么计算每种字符的贡献，显然把 $A$、$C$、$G$、$T$ 倒过来和 $A_*$、$C_*$、$G_*$、$T_*$ 做卷积即可。