← 返回题目列表

AtCoder · abc300_f

I. 更多假期

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个字符串 S 长度 N 组成 o 和 x和整数 M 和 K.
S 保证至少包含一个 x.

让 T 是长度的字符串 NM 通过连接获得 M 副本 S。 考虑完全更换 K x位于 T 与 o.
你的目标是拥有一个尽可能长的连续子字符串,其中包含 o 尽可能在结果中 T.
查找由以下组成的连续子字符串的最大长度 您可以获得的 o 。

约束

  • N, M,和 K 是整数。
  • 1 \le N \le 3 \times 10^5
  • 1 \le M \le 10^9
  • 1 \le K \le x,其中 x 是数量 x在字符串中 T.
  • S 是一个长度为的字符串 N 组成 o 和 x.
  • S 至少有一个 x.

输入

输入由标准输入按以下格式给出:

N M K
S

输出

将答案打印为整数。


示例输入 1

10 1 2
ooxxooooox

示例输出 1

9

S= ooxxooooox 和 T= ooxxooooox.
更换 x 在第三个和第四个字符处 o 使 T= ooooooooox.
现在我们有一个长度-9 连续子字符串组成 o,这是最长的可能。


示例输入 2

5 3 4
oxxox

示例输出 2

8

S= oxxox 和 T= oxxoxoxxoxoxxox.
更换 x 在 5,7,8 和 10第一个字符 o 使 T= oxxooooooooxxox.
现在我们有一个长度-8 连续子字符串组成 o,这是最长的可能。


示例输入 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

示例输出 3

19964887064