Advertisement
YEZAELP

PROG-1154: Longest Repeated Substring

Jun 26th, 2020
129
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.91 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using lli = long long;
  4. using pii = pair<int,int>;
  5. const lli PB = 98765431;
  6. string S;
  7. int main(){
  8.  
  9.     int n,mx=0,cnt,m;
  10.     scanf("%d%d",&n,&m);
  11.     cin>>S;
  12.  
  13.     int l=0,r=n-1;
  14.     while(l<=r){
  15.         int mid=(l+r)/2;
  16.         map <lli,int> cnt;
  17.         lli hsh=0, rem=1;
  18.         bool T=false;
  19.         for(int i=0;i<mid;i++){
  20.             if(i!=0) rem = rem*PB;
  21.             hsh = hsh*PB+S[i];
  22.         }
  23.         for(int i=0;i<n;i++){
  24.             if(i!=0) hsh = hsh*PB + S[i+mid-1];
  25.             cnt[hsh]++;
  26.             if(cnt[hsh]==m){
  27.                 T=true;
  28.                 break;
  29.             }
  30.             if(i+mid>=n) break;
  31.             hsh = hsh-rem*S[i];
  32.         }
  33.  
  34.         if(T) {
  35.             mx=max(mx,mid);
  36.             l = mid+1;
  37.         }
  38.         else  {
  39.             r = mid-1;
  40.         }
  41.     }
  42.  
  43.     printf("%d",mx);
  44.  
  45.     return 0;
  46. }
Advertisement
RAW Paste Data Copied
Advertisement