原题链接

题解

1.二分查找前缀出现次数，用 \(kmp\) 优化查找算法

code

#include<bits/stdc++.h>
using namespace std;
char s[200005];
int pre[200005]={0},occ[200005]={0};
int n,x;
int solve(int len)
{
    int cnt=1;
    int it=0;
    for(int j=len+1;j<=n;j++)
    {
        while(it&&s[it+1]!=s[j]) it=pre[it];
        if(s[it+1]==s[j]) it++;
        if(it==len)
        {
            cnt++;
            it=0;
        }
    }
    return cnt;
}

void init()
{
        pre[1]=0;
        for(int i=2;i<=n;i++)
        {
            int it=pre[i-1];
            while(it)
            {
                if(s[it+1]==s[i]) break;
                it=pre[it];
            }
            if(s[it+1]==s[i]) pre[i]=it+1;
            else pre[i]=0;
        }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>x>>x;
        cin>>(s+1);

        init();

        int l=0,r=n+1;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(solve(mid)>=x) l=mid;
            else r=mid;
        }

        cout<<l<<"\n";
    }
    return 0;
}