D-K匹配_牛客竞赛字符串专题班KMP1（字符串基本概念，KMP算法和简单应用）

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

题目描述

牛牛是赫赫有名的字符串高手，现在牛牛发现了一种新的匹配方式。给定一个字符串 $S$ 和一个字符串 $T$ ，如果 $S$ 存在一个长度为 $k$ 的子串 $S_{l_1, l_1 + k - 1}$ 和 $T$ 的某个长度为 $k$ 的子串 $T_{l_2,l_2 + k - 1}$ 相等，那么我们就认为字符串 $S$ 和字符串 $T$ 是 $k$ 匹配的。比如字符串 $abacc$ 和字符串 $ddabackk$ 就是 $4$ 匹配的。

牛牛知道这种匹配方式之后就迫不及待的想要提出新的问题。给定一个长度为 $n$ 的字符串 $S$ 和一个长度为 $k$ 的字符串 $T$ ，现在牛牛想知道 $S$ 有多少个子串和 $T$ 是满足 $k$ 匹配的。

本场大样例下载

输入描述:

第一行两个整数分别表示字符串的长度和字符串的长度。
第二行一个长度为的字符串表示。
第三行一个长度为的字符串表示。
保证字符串和中只包含小写字母。

输出描述:

输出一行整数表示中满足和是匹配的子串个数。

示例1

输入

复制

10 2
abaaaababa
ab

输出

复制

备注:

对于的数据满足
对于的数据满足
对于的数据满足
对于的数据满足