← 返回题目列表

Codeforces · 1302/I

I. 似曾相识

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

这是一次不寻常的比赛中的一个不寻常的问题,这里是公告:http://codeforces.com/blog/entry/73543

您经营一家琴弦店。在一天中,您的客户想要购买一定长度的字符串,有时还需要满足其他属性。

今天,您的第一位客户询问您是否有长度为 $$$k$$$ 的字符串。事实上,您有一个长度为 $$$n$$$ 的字符串,并且可以从其中的任何位置开始剪切长度为 $$$k$$$ 的字符串。您想知道这个字符串可以等于多少个不同的值。

请注意,在您的商店中,字符串超过了 $$$2$$$ 大小的字母表。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\leq k\leq n\leq 200\,000$$$)。第二行包含长度为$$$n$$$的二进制字符串$$$s$$$。

输出

在唯一的一行中打印字符串 $$$s$$$ 长度为 $$$k$$$ 的不同子字符串的数量。

示例

输入 #1

5 2
01101

输出 #1

3

输入 #2

10 3
1110001011

输出 #2

8

注意

第二个样本测试代表 3 阶 de Bruijn 序列。