/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は N 文字からなるリボンを持っており、左から順に英大文字からなる文字列 S が書かれています。
高橋君はこのリボンを、隣り合う文字と文字の間の相異なる位置で、合計 M 回以下切ることができます。
k 回切断すると、リボンは k + 1 個の空でない連続した断片に分かれます。各文字はちょうど 1 つの断片に含まれ、断片の順序は元の文字列 S における順序を保ちます。切断を 1 回も行わない場合、リボン全体が 1 つの断片となります。
断片に書かれた文字列がちょうど ATCODER であるとき、その断片を 当たり断片 と呼びます。
高橋君は、当たり断片の個数をできるだけ多くしたいです。
M 回以下の切断で得られる当たり断片の個数の最大値を求めてください。
制約
- 1 \leq N \leq 10^6
- 0 \leq M \leq N - 1
- S は英大文字からなる長さ N の文字列
- N, M は整数
入力
N M S
1 行目には、リボンの文字数 N と切断できる回数の上限 M が、スペース区切りで与えられる。
2 行目には、リボンに書かれた長さ N の文字列 S が与えられる。
出力
M 回以下の切断で得られる当たり断片の個数の最大値を、1 行で出力せよ。
入力例 1
7 0 ATCODER
出力例 1
1
入力例 2
14 1 ATCODERATCODER
出力例 2
2
入力例 3
54 8 HELLOATCODERWORLDATCODERATCODERXYZATCODERQQQATCODEREND
出力例 3
4
入力例 4
210 29 ATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODER
出力例 4
30
入力例 5
1 0 A
出力例 5
0
Score : 366 pts
Problem Statement
Takahashi has a ribbon consisting of N characters, with a string S of uppercase English letters written on it from left to right.
Takahashi can cut this ribbon at most M times at distinct positions between adjacent characters.
If he makes k cuts, the ribbon is divided into k + 1 non-empty contiguous pieces. Each character belongs to exactly one piece, and the order of the pieces preserves the order in the original string S. If no cuts are made, the entire ribbon remains as one piece.
A piece is called a winning piece if the string written on it is exactly ATCODER.
Takahashi wants to maximize the number of winning pieces.
Find the maximum number of winning pieces that can be obtained with at most M cuts.
Constraints
- 1 \leq N \leq 10^6
- 0 \leq M \leq N - 1
- S is a string of length N consisting of uppercase English letters
- N, M are integers
Input
N M S
The first line contains the number of characters on the ribbon N and the maximum number of cuts M, separated by a space.
The second line contains the string S of length N written on the ribbon.
Output
Print the maximum number of winning pieces that can be obtained with at most M cuts, on a single line.
Sample Input 1
7 0 ATCODER
Sample Output 1
1
Sample Input 2
14 1 ATCODERATCODER
Sample Output 2
2
Sample Input 3
54 8 HELLOATCODERWORLDATCODERATCODERXYZATCODERQQQATCODEREND
Sample Output 3
4
Sample Input 4
210 29 ATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODERATCODER
Sample Output 4
30
Sample Input 5
1 0 A
Sample Output 5
0