Score : $500$ points

问题描述

你得到一个长度为 $N$ 的字符串 $S$，其中包含字符 o 和 x，以及整数 $M$ 和 $K$。
保证字符串 $S$ 中至少包含一个 x。

令 $T$ 为通过将 $S$ 重复拼接 $M$ 次得到的长度为 $NM$ 的字符串。考虑在 $T$ 中恰好替换 $K$ 个 x 为 o。
你的目标是在变换后的 $T$ 中得到尽可能长的连续 o 子串。
找出你能得到的最长连续 o 子串的长度。

以上为通义千问 qwen-max 翻译，仅供参考。

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 and x.
• $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

update @ 2024/3/10 08:24:49