Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using lli=long long;
- int n,m;
- const lli pb=1e9+7;
- string c;
- bool check(int len){
- map<lli,lli> mp;
- lli hsh=0;
- lli base=1;
- for(int i=0;i<len;i++){
- hsh*=pb;
- hsh+=c[i]-'a';
- if(i!=0) base*=pb;
- }
- mp.insert(make_pair(hsh,1));
- for(int i=len;i<n;i++){
- hsh-=(c[i-len]-'a')*base;
- hsh*=pb;
- hsh+=c[i]-'a';
- if(mp.find(hsh)==mp.end()){
- mp.insert(make_pair(hsh,1));
- }else{
- mp[hsh]++;
- if(mp[hsh]>=m){
- return true;
- }
- }
- }
- return false;
- }
- int main(){
- scanf("%d%d",&n,&m);
- cin >> c;
- int l=1,r=n,ans=1;
- while(l<=r){
- int mid=(l+r)/2;
- if(check(mid)){
- ans=max(ans,mid);
- l=mid+1;
- }else{
- r=mid-1;
- }
- }
- printf("%d",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement