这是一次不寻常的比赛中的一个不寻常的问题,这里是公告: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 序列。