字符串匹配

时间限制：$1s$

空间限制：$256MB$

题目描述

给定误差阈值k，字符串 $S$，字符串 $T$，需要找到字符串$S$满足以下规则的位置$i$的数量。 当对齐 $T$ 的第一个字符和 $S$ 的第 $i$ 个字符后(对其需要将$T$对应到$S$中一段长度为$|T|$的子串上，即$1≤i≤|S|-|T|+1$)，$T$ 中的每一个字符能够在 $S$ 中找到一个位置误差不超过 $k$ 的相同字符（$S$中的某个字符可以被$T$中多个字符匹配）。即任何$j(1 ≤ j ≤ |T|)$，必定存在这样的$p(1 ≤ p ≤ |S|)$，满足 $|(i+j-1)-p|≤ k且S[p]=T[j]$.

数据格式

输入

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

第二行给出$S$，第三行给出$T$。

输出

输出一个整数，表示字符串$S$满足以下规则的位置$i$的数量。

样例

输入1

15 4 3
ABABABABCABCABC
CBAA

输出1

7

输入2

10 4 3
0101010101
1111

输出2

7

数据范围及约定

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

保证两个串出现字符种类不超过$100$