fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define ll long long
  7. #define lld long double
  8. #define ull unsigned long long
  9. #define left(a, v) lower_bound(a.begin(), a.end(), v)-a.begin()
  10. #define print(a) for (auto const& i : a) cout << i << "\n"; cout << "\n";
  11. using namespace std;
  12. const ll BASE = 31, LIM = 200005, MOD = 1e9 + 7;
  13. ll h[LIM]{0};
  14. ll power[LIM]{1};
  15. ll gethash(ll l, ll r) {
  16.   return (h[r] - h[l - 1] * power[r - l + 1] + MOD * MOD) % MOD;
  17. }
  18. void solve() {
  19.   ll n, l, r;
  20.   cin >> n >> l >> r; 
  21.   string s; 
  22.   cin >> s; 
  23.   for (ll i = 1; i <= n; i++){
  24.     power[i] = (power[i - 1] * BASE) % MOD;
  25.   }
  26.   ll k = l;
  27.   for (ll i = 1; i <= n; i++){
  28.     h[i] = (h[i - 1] * BASE + s[i - 1] - 'a' + 1) % MOD;
  29.   }
  30.   l = 1, r = n; ll res = 0;
  31.   while (l <= r) {
  32.     ll m = l + r >> 1;
  33.     ll d = 0;
  34.     ll f = gethash(1, m);
  35.     ll i = 1;
  36.     while ( m + 1 >= i) {
  37.       if (gethash(i, i+m-1) == f) {
  38.         d++;
  39.         i += m;
  40.       }
  41.       else i++;
  42.     }
  43.     if (d < k){
  44.     	r = m-1;
  45.     } 
  46.     else{
  47.       l = m + 1;
  48.       res = m;
  49.     }
  50.   }
  51.   cout << res << "\n";
  52. }
  53. int main() {
  54.   ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  55.   ll t;
  56.   cin >> t;
  57.   while (t--){
  58.     solve(); 
  59.   }
  60.   return 0;
  61. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
7
3 3 3
aba
3 3 3
aaa
7 2 2
abacaba
9 4 4
abababcab
10 1 1
codeforces
9 3 3
abafababa
5 3 3
zpozp
stdout
copy 
0
0
0
0
10
0
0
https://ideone.com/reeGPD
language:
C++14 (gcc 8.3)
created:
14 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!