fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define NMAX 50500
  3. using namespace std;
  4. const int base=256;
  5. const int mod=1e9+7;
  6. string s;
  7. int n,k;
  8. int Hash[NMAX],pw[NMAX+1];
  9. void prepare()
  10. {
  11.     cin>>n>>k>>s;
  12.     s='#'+s;
  13.     pw[0]=1;
  14.     for(int i=1;i<=NMAX;i++)  pw[i]=1ll*pw[i-1]*base%mod;
  15.  
  16.     for(int i=1;i<=n;i++)  Hash[i]=(Hash[i-1]+1ll*((int)s[i])*pw[i-1])%mod;
  17.  
  18.   //  for(int i=1;i<=n;i++)  cout<<Hash[i]<<" ";
  19. }
  20. int gethash(int l,int r)
  21. {
  22.     int temp=Hash[r]-Hash[l-1];
  23.     if(temp<0)  temp+=mod;
  24.     return 1ll*temp*pw[NMAX-l+1]%mod;
  25. }
  26. bool check_hash(int mask)
  27. {
  28.     map<int,int> mp;
  29.     for(int i=1;i<=n-mask+1;i++)
  30.     {
  31.         mp[gethash(i,i+mask-1)]++;
  32.     }
  33.     for(pair<int,int> u:mp)
  34.     {
  35.         if(u.second>=k) return true;
  36.     }
  37.     return false;
  38. }
  39. void process()
  40. {
  41.     int l=1,r=n,ans=1;
  42.     while(l<=r)
  43.     {
  44.         int mid=(l+r)>>1;
  45.         if(check_hash(mid))
  46.         {
  47.             ans=mid;
  48.             l=mid+1;
  49.         }
  50.         else
  51.         {
  52.             r=mid-1;
  53.         }
  54.  
  55.     }
  56.     cout<<ans;
  57.  
  58. }
  59. int main()
  60. {
  61.     ios_base::sync_with_stdio(0);
  62.     cin.tie(0);
  63.     cout.tie(0);
  64.     prepare();
  65.     process();
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/L1XrHs
language:
C++14 (gcc 8.3)
created:
175 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!