C-Fuzzy Search_牛客竞赛数学专题班FFT与拉格朗日插值（FFT、快速多项式乘法、拉格朗日插值）

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一个门限值 $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$ 开始。)

输入描述:

第一行有三个整数  ,  ,  ，表示  的长度，  的长度和"门限值"。 

第二行给出基因串，第三行给出基因串，且两个串都只包含大写字母 。

输出描述:

输出一个整数，表示  在  中出现的次数。

示例1

输入

复制

10 4 1
AGCAATTCAT
ACAT

输出

复制

备注:

原题链接：https://codeforces.com/problemset/problem/528/D