不同子串

题目描述

统计一个长度为$n$的只包含小写字母的字符串有多少个不同的长度为$m$的子串。

输入格式

第一行输入一个整数$n$，$m$。

第二行输入一个长度为$n$的字符串。

输出格式

表示问题的答案。

数据范围与提示

• 对于$30\%$的数据，$1 \leq m \leq n \leq 200$；
• 对于$50\%$的数据，$1 \leq m \leq n \leq 2000$；
• 对于另外$20\%$的数据，$1 \leq m \leq 50 \leq n \leq 200000$；
• 对于$100\%$的数据，$1 \leq m \leq n \leq 200000$。

样例

5 3
aaaab

2

说明

长度为$3$的子串有$3$个，分别是$aaa$，$aaa$，$aab$，其中不同的只有$2$个。

9 3
abcabacba

7

说明

共有$7$个长度为$3$的子串，每个长度为$3$的子串都不同。