分数: 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