最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 文章评分

C++ 少儿编程 1111浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

nodgd的文章由$n$个小写英文字母组成。文章的一个子串指的是文章中的一段连续的字母,子串的长度就是这一段的字母个数。nodgd在文章中用了排比、对偶、前后照应之类的手法,所以就有很多个子串是相同或者相近的。为了向大家证明这是一篇好文章,nodgd决定给自己的文章进行评分。nodgd 首先确定了一个整数$m$,然后统计出文章中有多少个不相同的长度为$m$的子串,这个数量就是文章的评分。

【输入】

第一行包含两个整数$n,m$,表示文章的长度和需要统计的子串长度。

第二行包含一个长度为$n$的只包含小写字母的字符串。

【输出】

一行一个整数,表示文章的评分。

【输入样例】

5 3 
aaaab

【输出样例】

2

【提示】

【样例解释1】

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

【输入样例2】

9 3 
abcabacba

【输出样例2】

7

【样例解释2】

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

【数据规模】

对于 30%的数据,$1≤m≤n≤200$。

对于 50%的数据,$1≤m≤n≤2000$。

对于另外 20%的数据,$1≤m≤50≤n≤200000$。

对于 100%的数据,$1≤m≤n≤200000$。

您必须 登录 才能发表评论!