\(T\) の中で最も長く o が連続するような部分の先頭の文字を全探索できればこの問題に正解できます ( が、当然 \(NM\) 通りを素直に全探索することはできません )。

以下の補題を示しましょう。

最も長く o が連続するような部分の先頭の文字が \(N\) 文字目以前であるような最適解が存在する。

ある最適解に着目したとき、最も長く o が連続するような部分の先頭の文字が \(N+1\) 文字目以降にあったとします。この時、全ての変更について \(i\) 文字目を変更した場合は(存在すれば) \(i-N\) 文字目を変更するように改めます。
すると、最も長く o が連続するような部分の先頭の文字が \(N\) 文字前に移動した最適解が得られます。これを繰り返すことで補題を証明できます。

今、問題は以下に帰着されました。

全ての \(i=1,2,\dots,N\) について以下の問題を解け。
\(T\) の \(i\) 文字目を始点としてなるだけ多くの o を連続させたい。可能な最大の長さを求めよ。

この問題は以下のようにして解くことができます。

• 可能な最も遠い終点の位置を二分探索する。
  • 二分探索の判定は、始点と終点の間にある x の数が \(K\) 以下かどうかで調べられる。

上記の二分探索を実現するにあたって 「 \(T\) の \(i\) 文字目までに x は何個含まれるか? 」の質問に高速に解答したくなりますが、これは \(T\) の周期性と累積和を使えば \(O(1)\) で実現可能です。詳しくは実装例も参照してください。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

long long f(long long x,long long n,vector<long long> &rw){
  long long res=(x/n)*rw[n];
  long long rem=x%n;
  res+=rw[rem];
  return res;
}

int main(){
  long long n,m,k;
  string s;
  cin >> n >> m >> k >> s;
  
  vector<long long> rw(n+1,0);
  for(long long i=0;i<n;i++){
    rw[i+1]=rw[i];
    if(s[i]=='x'){rw[i+1]++;}
  }

  long long res=0;
  for(long long i=1;i<=n;i++){
    long long fbeg=f(i-1,n,rw);
    long long l=i,r=n*m;
    while(l<=r){
      long long te=(l+r)/2;
      if(f(te,n,rw)-fbeg<=k){l=te+1;}
      else{r=te-1;}
    }
    res=max(r-i+1,res);
  }
  cout << res << "\n";
  return 0;
}