考虑一个二分。
发现固定起始点,二分终点是一个不错的想法。
由于直接求一段内 x
的个数不怎么现实,所以考虑进行前缀和转化。
于是问题转化为了如何求 $1$ 到 $a$ 的 x
的个数。
分为两部分,循环的部分和零散部分。
最后,注意二分边界。
AC 代码(细节在注释中):
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MT int TTT=R;while(TTT--)
#define pc putchar
#define R read()
#define fo(i,a,b) for(register int i=a;i<=b;i++)
#define rep(i,a,b) for(register int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
int read()
{
int x=0;
char ch=getchar();
bool f=0;
while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f) x=-x;
return x;
}
template<typename T> inline void write(T x)
{
if(x<0)
{
pc('-');
x=-x;
}
if(x>9) write(x/10);
pc(x%10+'0');
}
const int mod=998244353;
int qmi(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
const int N=3e5+10;
int n,m,k,ans;
string S;//输入的字符串
int s[N];//1~i(小范围)的字符 x 的个数
int calc(int x)//1~x 的字符 x 的个数
{
return s[n]*(x/n)+s[x%n];
}
signed main(){
n=R,m=R,k=R;
cin>>S,S='>'+S;//方便处理下标
fo(i,1,n) s[i]=s[i-1]+(S[i]=='x');//小范围的预处理
fo(i,1,n) if(!(S[i]=='x'&&k==0))//这个 if 是为了防止二分出来的答案无法实施
{
int l=i,r=n*m;
while(l<r)
{
int mid=l+r+1>>1;//注意二分边界!
if(calc(mid)-s[i-1]<=k) l=mid;
else r=mid-1;
}
ans=max(ans,l-i+1);
}
write(ans);
}