More Holidays

题目描述

给你一个由 $o$ 和 $x$ 组成且长度为 $N$ 的字符串 $S$，以及整数 $M$ 和 $K$。
已知 $S$ 至少包含一个 $x$。 令 $T$ 为通过将 $S$ 连续连接 $M$ 次得到的长度为 $NM$ 的字符串。 考虑在 $T$ 中恰好将 $K$ 个 $x$ 替换为 $o$。
你的目标是在得到的 $T$ 中尽可能获得最长的由 $o$ 组成的连续子串。
求你能获得的由 $o$ 组成的连续子串的最大长度。

输入格式

输入按照标准输入呈现，格式如下： $N$ $M$ $K$ $S$

输出格式

输出答案，一个整数。

10 1 2
ooxxooooox

9

5 3 4
oxxox

8

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

19964887064

提示

$N$、$M$ 和 $K$ 是整数。 $1 \le N \le 3 \times 10^5$ $1 \le M \le 10^9$ $1 \le K \le x$，其中 $x$ 是字符串 $T$ 中的 $x$ 的数量。 $S$ 是一个长度为 $N$ 的由 $o$ 和 $x$ 组成的字符串。 $S$ 至少包含一个 $x$。$S=$ $ooxxooooox$ 且 $T=$ $ooxxooooox$.
将第三和第四个字符处的 $x$ 替换为 $o$ 可使 $T=$ $ooooooooox$.
现在我们有一个长度为 $9$ 的由 $o$ 组成的连续子串，这是可能的最长长度。
$S=$ $oxxox$ 且 $T=$ $oxxoxoxxoxoxxox$.
将第 $5,7,8$ 和 $10$ 个字符处的 $x$ 替换为 $o$ 可使 $T=$ $oxxooooooooxxox$.
现在我们有一个长度为 $8$ 的由 $o$ 组成的连续子串，这是可能的最长长度。

标签: AtCoder|abc300F

来源

AtCoder|abc300F