牛客练习赛61 - E 相似的子串

传送门：牛客练习赛61 - E

思路分析

很显然，答案具有二分性，二分前缀的长度
开一个map记录hash值的上一个位置，枚举每一个长度为mid的前缀
如果距离上一个map的位置，说明不想交，这个前缀的计数+1
如果存在一个前缀的次数$≥k$，说明该长度成立

样例输入

7 3
abcabab

样例输出

2

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int base= 10001659;
const int mod=100000429;
const int N=2e5+10;

char s[N];
int n,k;
ll ha[N],ba[N];
unordered_map<ll,int>pos,cnt;

ll get(int l,int r) {
    ll ans=(ha[r]-ha[l-1]*ba[r-l+1]+mod)%mod;
    if(ans<0) ans+=mod;
    return ans;
}

int judge(int len) {
    pos.clear();
    cnt.clear();
    for(int i=len; i<=n; i++) {
        ll x=get(i-len+1,i);
        if(!pos[x] || i-pos[x]>=len) {
            pos[x]=i;
            cnt[x]++;
        }
        if(cnt[x]>=k) return 1;
    }
    return 0;
}


int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>k>>s+1;
    ba[0]=1;
    for(int i=1; i<=n; i++) {
        ba[i]=ba[i-1]*base%mod;
        ha[i]=(ha[i-1]*base)%mod+s[i];
    }
    int l=0,r=n/k;
    int ans;
    while(r>=l){
        int mid=l+r>>1;
        if(judge(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans<<endl;





    return 0;
}