fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4.  
  5. const ll MOD = 1e9 + 7;
  6. const int MAXN = 50001;
  7. const ll base = 311;
  8.  
  9. int n,k;
  10. char s[MAXN];
  11. ll power[MAXN], hash_[MAXN];
  12. ll f[MAXN], h[MAXN];
  13.  
  14. ll get_hash(int i, int j){
  15.     return (hash_[j] - hash_[i-1]*power[j-i+1] + MOD*MOD)%MOD;
  16. }
  17.  
  18.  
  19. int main(){
  20.     cin >> n >> k;
  21.     for (int i=1; i<=n; i++){
  22.         cin >> s[i];
  23.     }
  24.  
  25.     power[0] = 1;
  26.     for (int i=1; i<=n; i++){
  27.         power[i] = (power[i-1]*base)%MOD;
  28.     }
  29.  
  30.     for (int i=1; i<=n; i++){
  31.         hash_[i] = (hash_[i-1]*base + (ll)s[i])%MOD;
  32.     }
  33.  
  34.     int ans = 0, l = 1, r = n;
  35.     while(l<=r){
  36.         int mid = (l+r)/2;
  37.         for (int i=1; i<= n - mid + 1; i++){
  38.             h[i] = get_hash(i,i+mid-1);
  39.         }
  40.         sort(h+1,h+n-mid+2);
  41.         f[1] = 1;
  42.         bool check = false;
  43.         for (int i=2; i<= n - mid + 1; i++){
  44.             if (h[i] == h[i-1]) f[i] = f[i-1] + 1;
  45.             else f[i] = 1;
  46.             if (f[i] >= k){
  47.                 check = true;
  48.                 break;
  49.             }
  50.         }
  51.         if (check){
  52.             ans = mid;
  53.             l = mid+1;
  54.         } else r = mid-1;
  55.     }
  56.     cout << ans;
  57. }
  58.  
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
5 2
xxxxx
stdout
copy 
4
https://ideone.com/ZtlgCT
language:
C++14 (gcc 8.3)
created:
254 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!