题目描述

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

输入格式

第一行有三个整数 $n$ , $m$ , $k$ ，表示 $S$ 的长度， $T$ 的长度和"门限值"。

第二行给出基因串$S$，第三行给出基因串$T$，且两个串都只包含大写字母$\texttt{ATGC}$ 。

$1≤n≤m≤2*10^5\ ,\ 0≤k≤2*10^5$

输出格式

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

10 4 1
AGCAATTCAT
ACAT

3