実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
o
と x
からなる長さ N の文字列 S と、整数 M,K が与えられます。
S には少なくとも 1 つの x
が含まれることが保証されます。
S を M 個連結して得られる長さ NM の文字列を T とします。
T に含まれる x
のうち丁度 K 個を選んで o
に変えることを考えます。
あなたの目標は、変更後の T に o
のみからなるできるだけ長い連続部分文字列が含まれるようにすることです。
o
のみからなる連続部分文字列の長さとして達成可能な最大値を求めてください。
制約
- N,M,K は整数
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- x を文字列 T に含まれる
x
の総数としたとき、 1 \le K \le x - S は
o
とx
からなる長さ N の文字列 - S には少なくとも 1 つの
x
が含まれる
入力
入力は以下の形式で標準入力から与えられる。
N M K S
出力
答えを整数として出力せよ。
入力例 1
10 1 2 ooxxooooox
出力例 1
9
S= ooxxooooox
、 T= ooxxooooox
です。
3 文字目と 4 文字目の x
を o
に変更することにより、変更後の T= ooooooooox
となります。
このとき o
のみからなる長さ 9 の連続部分文字列が得られ、これが達成可能な最大値です。
入力例 2
5 3 4 oxxox
出力例 2
8
S= oxxox
、 T= oxxoxoxxoxoxxox
です。
5,7,8,10 文字目の x
を o
に変更することにより、変更後の T= oxxooooooooxxox
となります。
このとき o
のみからなる長さ 8 の連続部分文字列が得られ、これが達成可能な最大値です。
入力例 3
30 1000000000 9982443530 oxoxooxoxoxooxoxooxxxoxxxooxox
出力例 3
19964887064
Score : 500 points
Problem Statement
You are given a string S of length N consisting of o
and x
, and integers M and K.
S is guaranteed to contain at least one x
.
Let T be the string of length NM obtained by concatenating M copies of S.
Consider replacing exactly K x
's in T with o
.
Your objective is to have as long a contiguous substring consisting of o
as possible in the resulting T.
Find the maximum length of a contiguous substring consisting of o
that you can obtain.
Constraints
- N, M, and K are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le M \le 10^9
- 1 \le K \le x, where x is the number of
x
's in the string T. - S is a string of length N consisting of
o
andx
. - S has at least one
x
.
Input
The input is given from Standard Input in the following format:
N M K S
Output
Print the answer as an integer.
Sample Input 1
10 1 2 ooxxooooox
Sample Output 1
9
S= ooxxooooox
and T= ooxxooooox
.
Replacing x
at the third and fourth characters with o
makes T= ooooooooox
.
Now we have a length-9 contiguous substring consisting of o
, which is the longest possible.
Sample Input 2
5 3 4 oxxox
Sample Output 2
8
S= oxxox
and T= oxxoxoxxoxoxxox
.
Replacing x
at the 5,7,8 and 10-th characters with o
makes T= oxxooooooooxxox
.
Now we have a length-8 contiguous substring consisting of o
, which is the longest possible.
Sample Input 3
30 1000000000 9982443530 oxoxooxoxoxooxoxooxxxoxxxooxox
Sample Output 3
19964887064