2086: Alban's Jedi Code Decryption

文件提交:无需freopen 内存限制:512 MB 时间限制:3.000 S
评测方式:普通裁判 命题人:
提交:1 解决:1

题目描述

In the ancient archives of the Jedi Temple, Alban discovered a mysterious code pattern: as long as the letters P, C, K appear in order (not necessarily contiguously) within a string, it represents a valid "Jedi Code".

But a simple discovery is no longer enough for Alban's curiosity. He decides to find out how many intervals (substrings) exist such that the number of Jedi Codes appearing within that interval is no less than his Force sensitivity threshold $L$.

For example, if the threshold $L = 2$ and the string is PCCKA. In this string:

  • The 1st P, 2nd C, and 4th K form one PCK.

  • The 1st P, 3rd C, and 4th K form another PCK.

    In total, there are 2 PCKs. Therefore, the intervals where the number of PCK occurrences is $\ge 2$ are [1,4] (PCCK) and [1,5] (PCCKA), for a total of 2.

Given the threshold $L$ and the string $S$, please help Alban calculate how many intervals have $\ge L$ occurrences of the Jedi Code.

输入

$$\begin{aligned} &N \; L \\ &S \end{aligned}$$
  • First line: The string length $N$ ($3 \leq N \leq 200,000$) and the Force sensitivity threshold $L$ ($1 \leq L \leq 10^{15}$)

  • Second line: A string $S$ of length $N$ consisting of uppercase English letters.

输出

Output the number of intervals that satisfy the condition.

样例输入

5 2
PCCKA

样例输出

2

提示

来源/分类