fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #ifdef OP_DEBUG
  4.     #include <algo/debug.h>
  5. #else
  6.     #define debug(...) 26
  7. #endif
  8.  
  9. using namespace std;
  10.  
  11. #define int 	long long
  12. #define sz(v)   (int)(v).size()
  13. #define all(v)  (v).begin(), (v).end()
  14. #define TcT     template <class T
  15.  
  16. const   int     MOD = (int)1e9 + 7, INF = (int)4e18 + 18;
  17.  
  18. TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
  19. TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }
  20.  
  21. void solve();
  22.  
  23. int32_t main() {
  24.     cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
  25.     int testcases = 1;
  26.  
  27. #define TC 0
  28.     if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
  29. }
  30.  
  31. /* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */
  32.  
  33. template <int Mod, int Base>
  34. struct Hashing {
  35.     int n;
  36.     vector <int> Num;
  37.     vector <int> prefHash, suffHash;
  38.     vector <int> Pow;
  39.  
  40. public:
  41.     Hashing(){}
  42.     Hashing(const string &s) {
  43.         n = sz(s);
  44.         Num.assign(n + 1, 0);
  45.         prefHash.assign(n + 1, 0), suffHash.assign(n + 2, 0);
  46.         Pow.assign(n + 1, 0);
  47.  
  48.         for (int i = 0; i < n; ++i)
  49.             Num[i + 1] = s[i] - 'a' + 1;
  50.     }
  51.     Hashing(const vector <int> &num) { // idx from 1
  52.         n = sz(num) - 1;
  53.         Num.assign(n + 1, 0);
  54.         prefHash.assign(n + 1, 0), suffHash.assign(n + 2, 0);
  55.         Pow.assign(n + 1, 0);
  56.  
  57.         for (int i = 1; i <= n; ++i)
  58.             Num[i] = num[i];
  59.     }
  60.  
  61.     void init()                   { return void(initialize()); }
  62.  
  63.     int getPrefHash(int l, int r) { return getPref(l, r);      } // idx from 1
  64.     int getSuffHash(int l, int r) { return getSuff(l, r);      } // idx from 1
  65.  
  66.     bool isPalin()                { return palin(1, n);        }
  67.     bool isPalin(int l, int r)    { return palin(l, r);        }
  68.  
  69. private:
  70.     void initialize() {
  71.         Pow[0] = 1;
  72.         for (int i = 1; i <= n; ++i)
  73.             Pow[i] = (Pow[i - 1] * Base) % Mod;
  74.  
  75.         for (int i = 1; i <= n; ++i) {
  76.             prefHash[i] = (prefHash[i - 1] * Base + Num[i]) % Mod;
  77.             suffHash[n - i + 1] = (suffHash[n - i + 2] * Base + Num[n - i + 1]) % Mod;
  78.         }
  79.     }
  80.  
  81.     int getPref(int left, int right) { // idx from 1
  82.         return (prefHash[right] - prefHash[left - 1] * Pow[right - left + 1] + Mod * Mod) % Mod;
  83.     }
  84.  
  85.     int getSuff(int left, int right) {
  86.         return (suffHash[left] - suffHash[right + 1] * Pow[right - left + 1] + Mod * Mod) % Mod;
  87.     }
  88.  
  89.     bool palin(int l, int r) {
  90.         return getPref(l, r) == getSuff(l, r);
  91.     }
  92. };
  93.  
  94. using Hash = Hashing <MOD, 31>;
  95.  
  96. bool check(int len, int n, int k, Hash &H) {
  97.     map <int, int> cnt;
  98.     for (int i = 1; i <= n - len + 1; ++i)
  99.         if (++cnt[H.getPrefHash(i, i + len - 1)] >= k)
  100.             return true;
  101.  
  102.     return false;
  103. }
  104.  
  105. void solve() {
  106.     int n, k; cin >> n >> k;
  107.     string s; cin >> s;
  108.  
  109.     Hash H(s); H.init();
  110.  
  111.     int ans = 0;
  112.     int lo = 1, hi = n;
  113.     while (lo <= hi) {
  114.         /// dap an la 3
  115.         int mid = (lo + hi) >> 1;
  116.  
  117.         if (check(mid, n, k, H))
  118.             ans = mid, lo = mid + 1;
  119.         else
  120.             hi = mid - 1;
  121.     }
  122.  
  123.     cout << ans << '\n';
  124. }
  125.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/jSMDiX
language:
C++14 (gcc 8.3)
created:
30 days ago
visibility:
public

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!