小宝是赫赫有名的字符串高手，现在小宝发现了一种新的匹配方式，给定一个字符串。S存在一个长度为。相等，那么我们就认为字符串。S有多少个子串和
小宝是赫赫有名的字符串高手，现在小宝发现了一种新的匹配方式。给定一个字符串 S S和一个字符串 T T，如果 S S存在一个长度为 k k的子串 S_{l_1, l_1 + k - 1} S l 1 ,l 1 +k−1 和 T T的某个长度为 k k的子串 T_{l_2,l_2 + k - 1} T l 2 ,l 2 +k−1 相等，那么我们就认为字符串 S S和字符串 T T是 k k匹配的。比如字符串 abacc abacc和字符串 ddabackk ddabackk就是 4 4匹配的。 小宝知道这种匹配方式之后就迫不及待的想要提出新的问题。给定一个长度为 n n的字符串 S S和一个长度为 k k的字符串 T T，现在小宝想知道 S S有多少个子串和 T T是满足 k k匹配的。 本场大样例下载
（图片来源网络，侵删）
