← 返回题目列表

Codeforces · 528/D

D. 模糊搜索

中文机器翻译题面 查看原题

Leonid 为一家规模虽小但前景远大的初创公司工作,该公司致力于解码人类基因组。他的职责包括解决这样一类复杂问题:在由字母 'A'、'T'、'G' 和 'C' 组成的长字符串中寻找特定模式。

让我们考虑如下情形。现在有一段记录为字符串 S 的人类 DNA 链片段。为了分析该片段,需要在字符串 S 中找到字符串 T 的所有出现位置。然而,问题因原始链片段可能包含一些微小突变而变得复杂,尽管这些突变很小,却增加了寻找片段的难度。Leonid 提出了以下方法来解决这个问题。

记整数 k ≥ 0 为错误阈值。我们称字符串 T 在字符串 S 的位置 i(1 ≤ i ≤ |S| - |T| + 1)处出现,当把字符串 T 从该位置开始对齐后,字符串 T 的每个字符都能在字符串 S 中找到一个值相同的字符,且两者的位置距离至多为 k。更形式化地说,对于任意 j(1 ≤ j ≤ |T|),都必须存在某个 p(1 ≤ p ≤ |S|),使得 |(i + j - 1) - p| ≤ k 且 S[p] = T[j]。

例如,根据上述定义,字符串“ACAT”在字符串“AGCAATTCAT”中的位置 2、3 和 6 处出现。

注意,当 k = 0 时,上述定义就变成了字符串在另一个字符串中出现的简单定义。

请帮助 Leonid 计算给定字符串 T 在给定字符串 S 中按照给定错误阈值出现的位置数。

输入

第一行包含三个整数 |S|, |T|, k(1 ≤ |T| ≤ |S| ≤ 200 000,0 ≤ k ≤ 200 000)— 字符串 S 和 T 的长度以及错误阈值。

第二行包含字符串 S。

第三行包含字符串 T。

两个字符串均只由大写字母 'A'、'T'、'G' 和 'C' 组成。

输出

按照上述定义,输出一个数字,即字符串 T 在字符串 S 中以错误阈值 k 出现的次数。

示例

输入
复制

10 4 1
AGCAATTCAT
ACAT

输出
复制

3

注

如果你对人类基因组结构的了解碰巧比本题作者更多,并且对 Leonid 最初提出的方法不以为然,那么不必认真对待上面所描述的一切。