解法
部分問題として，\(M=1\) のときを考える． \(s\)のうち，丁度\(k\)個の x を o に変えた後の 最大の o の長さを求める．
補助的な配列 \(a\)を用意する． 大体は，\(s\) の x の部分を \(0\) にして，o の部分を長さとする． ただし，0 が並ぶ個数は，(x が並ぶ個数 - 1) となる様にする． また，\(s_{-1} = \) x とする． \(a\)から連続する (\(k+1\) 個の和 + \(k\)) の最大が答え．
本問に戻ると，\( M \geq 2\) の場合は，真ん中は周期性を使って簡単に求まるので， 両端だけ考えれば十分． よって，\(s+s\) に対する部分問題に帰着する．
注意
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// sのうち，xを丁度 k個 o に変える
ll solve(string s, ll k){
if(k < 0) return 0;
ll n = s.length();
vll a; a.push_back(0);
rep(i,n){
if(s[i] == 'o') a.back()++;
if(s[i] == 'x') a.push_back(0);
}
if(a.size() < k+1) return 0;
// a から連続する，丁度 k+1 個の和をとる．
ll tot = 0; rep(i,k) tot += a[i];
ll res = 0;
srep(i,k,a.size()){
tot += a[i];
chmax(res, tot);
tot -= a[i-k];
}
return res + k; // rem: + k
}
int main() {
ll n,m,k;
cin >> n >> m >> k;
string s; cin >> s;
ll x = 0; rep(i,n) x += s[i]=='x';
if(m == 1){
cout << solve(s, k) << endl;
return 0;
}
ll c = k/x;
chmin(c, m-2);
k -= x*c;
ll ans = c*n;
ans += solve(s+s, k);
cout << ans << endl;
return 0;
}
