CF528D Fuzzy Search

Leonid works for a small and promising start-up that works on decoding the human genome. His duties include solving complex problems of finding certain patterns in long strings consisting of letters 'A', 'T', 'G' and 'C'. Let's consider the following scenario. There is a fragment of a human DNA chain, recorded as a string $ S $ . To analyze the fragment, you need to find all occurrences of string $ T $ in a string $ S $ . However, the matter is complicated by the fact that the original chain fragment could contain minor mutations, which, however, complicate the task of finding a fragment. Leonid proposed the following approach to solve this problem. Let's write down integer $ k>=0 $ — the error threshold. We will say that string $ T $ occurs in string $ S $ on position $ i $ ( $ 1

The first line contains three integers $ |S|,|T|,k $ ( $ 1

Print a single number — the number of occurrences of $ T $ in $ S $ with the error threshold $ k $ by the given definition.

If you happen to know about the structure of the human genome a little more than the author of the problem, and you are not impressed with Leonid's original approach, do not take everything described above seriously.