设第一部分的长度为 x（0 \le x < N），则第一部分为 S_{N-x+1} \sim S_{N}。
设第三部分的长度为 x（0 \le x < N），则第三部分为 S_{1} \sim S_{x}。
假设 S 中 x 的数量为 y，那么为了使答案最大，第二部分字符串 S 的数量是 \min(\lfloor \frac{K}{y} \rfloor,M-2)（减 2 表示减掉第一部分和第三部分），但还有一种情况，第二部分字符串的数量是 \min(\lfloor \frac{K}{y} \rfloor - 1,M-2)，将多出来的 N 次修改机会放到第一部分和第三部分。接着我们对于这两种情况将 K 减去第二部分字符串 S 的数量乘 y，就是第一部分和第三部分的修改次数。
再不难发现，对于复制了 M 次的（M>1）字符串第一部分和第三部分拼起来是连续的，此时我们可以使用双指针算法求出修改后全为 o 的子串的最大长度：
当 $S_{l} \sim S_{r}$ 中 `x` 的数量大于 $K$ 时，就不断右移左指针，虽然题目中要求恰好改变 $K$ 个字符，但实际上移动后的 $S_{l} \sim S_{r}$ 中 `x` 的数量只要小于等于 $K$，$r-l+1$ 就可以与当前答案取最大值了，因为多出来的可以放到剩下任意位置。
需要注意的是：如果 $K > y$，那么答案字符串一定由那三部分组成，但反之则不一定，随便在 $S'$ 中截取一段即可。还有：当 $M=1$ 时 $K$ 一定小于等于 $y$，并且无需将 $S$ 复制一遍。
## AC Code
```cpp
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
template<typename T> void read(T &x) { int f = 1; x = 0; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = getchar(); }while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }x *= f; }
template<typename T, typename ...Args> void read(T &x, Args &...args) { read(x); read(args...); }
template<typename T> void print(T x) { if (x < 0) { putchar('-'); x = -x; }if (x > 9) { print(x / 10); }putchar(char(x % 10 + 48)); }
template<typename T, typename ...Args> void print(T x, Args ...args) { print(x); putchar(' '); print(args...); }
const int INT_INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T1, typename T2> T1 _pow(T1 a, T2 b) { T1 x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------
// ----------------------------
// ----------------------------
int main() {
long long n, m, k; read(n, m, k);
string s; cin >> s;
// ----------------------------
int l = 0; long long cnt = 0, maxn = 0, ans = 0;
for (int i = 0; i < n; i++) cnt += (s[i] == 'x');
if (cnt * m <= k) {
print(n * m);
return 0;
}
if (m > 1) s += s;
if (k <= cnt) {
long long t = 0; // 表示 s[l]~s[r] 中 x 的数量
for (int r = 0; r < (int)s.length(); r++) {
t += (s[r] == 'x');
while (l < r && t > k) t -= (s[l++] == 'x');
if (t <= k) maxn = max(maxn, r - l + 1 - t);
}
ans = max(ans, maxn + k);
}
else {
long long x = min(k / cnt * n, (m - 2) * n); l = 0; maxn = 0; // x 表示第二部分的长度
long long w = k - min(k / cnt * cnt, (m - 2) * cnt); // 表示第一部分和第三部分的可修改次数
long long t = cnt - (s[n - 1] == 'x'); // 表示 s[l]~s[r] 中 x 的数量
for (int r = n - 1; r < n * 2; r++) {
t += (s[r] == 'x');
while (l < r && l < n && t > w) t -= (s[l++] == 'x');
if (t <= w) maxn = max(maxn, r - l + 1ll);
}
ans = max(ans, x + maxn);
x = min((k / cnt - 1) * n, (m - 2) * n); l = 0; maxn = 0;
w = k - min((k / cnt - 1) * cnt, (m - 2) * cnt);
t = cnt - (s[n - 1] == 'x');
for (int r = n - 1; r < n * 2; r++) {
t += (s[r] == 'x');
while (l < r && l < n && t > w) t -= (s[l++] == 'x');
if (t <= w) maxn = max(maxn, r - l + 1ll);
}
ans = max(ans, x + maxn);
}
// ----------------------------
print(ans);
return 0;
}
```