3648: K 匹配(第五轮02)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
牛牛是赫赫有名的字符串高手，现在牛牛发现了一种新的匹配方式。给定一个字 符串 S 和一个字符串 T，如果 S 存在一个长度为 k 的子串Sl1,l1 +K−1和 T 的 某个长度为 k 的子串 Tl2,l2 +K−1 相等， 那么我们就认为字符串 S 和字符串 T 是 k 匹配的。比如字符串 abacc 和字符串 ddabackk 就是 4 匹配的。
牛牛知道这种匹配方式之后就迫不及待的想要提出新的问题。给定一个长度为n 的字符串 S 和一个长度为 k 的字符串 T，现在牛牛想知道 S 有多少个子串和 T 是满足 k 匹配的。
输入
第一行两个整数 n, k 分别表示字符串 S 的长度和字符串 T 的长度。 第二行一个长度为 n 的字符串表示 S。
第三行一个长度为 k 的字符串表示 T 。 保证字符串 S 和 T 中只包含小写字母。
输出
对输出一行整数表示 S 中满足和 T 是 k 匹配的子串个数。
样例输入 复制
10 2
abaaaababa
ab样例输出 复制
33提示
【数据范围】
对于20%的数据满足1 ≤ k ≤ n ≤ 500
对于40%的数据满足1 ≤ k ≤ n ≤ 5000
对于60%的数据满足1 ≤ k ≤ n ≤ 1e6
对于100%的数据满足1 ≤ k ≤ n ≤ 1e7