fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 1e5;
  12. const int MOD = 1e9 + 7;
  13. const int BASE = 256;
  14.  
  15. int n, mx_cnt = 0, mx_len;
  16. string s;
  17. ll h[maxn + 10], p[maxn + 10];
  18. unordered_map<ll, int> mp;
  19. ii mx = {0, 0};
  20.  
  21. ll get_hash(int l, int r)
  22. {
  23.     ll a = h[r] - h[l - 1] * p[r - l + 1] % MOD;
  24.     a %= MOD;
  25.     a += MOD;
  26.     return a % MOD;
  27. }
  28. bool check(int x)
  29. {
  30.     mp.clear();
  31.     int mx = 0;
  32.     for (int i = 1; i <= n - x + 1; i++)
  33.     {
  34.         mp[get_hash(i, i + x - 1)]++;
  35.         mx = max(mx, mp[get_hash(i, i + x - 1)]);
  36.     }
  37.     return mx >= mx_cnt;
  38. }
  39. int bs(int l, int r)
  40. {
  41.     int ans = l;
  42.     while (l <= r)
  43.     {
  44.         int m = l + r >> 1;
  45.         if (check(m))
  46.         {
  47.             ans = m;
  48.             l = m + 1;
  49.         }
  50.         else
  51.             r = m - 1;
  52.     }
  53.     return ans;
  54. }
  55. bool cmp(int i, int j)
  56. {
  57.     int l = 1;
  58.     int r = mx_len;
  59.     int ans = 0;
  60.     while (l <= r)
  61.     {
  62.         int m = l + r >> 1;
  63.         if (get_hash(i, i + m - 1) == get_hash(j, j + m - 1))
  64.         {
  65.             ans = m;
  66.             l = m + 1;
  67.         }
  68.         else
  69.             r = m - 1;
  70.     }
  71.     if (ans == mx_len)
  72.         return 0;
  73.     return s[i + ans] < s[j + ans];
  74. }
  75.  
  76. int main()
  77. {
  78.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  79.     if (fopen("COUNTSTR.INP", "r"))
  80.     {
  81.         freopen("COUNTSTR.INP", "r", stdin);
  82.         freopen("COUNTSTR.OUT", "w", stdout);
  83.     }
  84.  
  85.     cin >> s;
  86.     n = s.size();
  87.     s = ' ' + s;
  88.     p[0] = 1;
  89.     for (int i = 1; i <= n; i++)
  90.     {
  91.         p[i] = p[i - 1] * BASE % MOD;
  92.         h[i] = (h[i - 1] * BASE + s[i]) % MOD;
  93.     }
  94.     for (int i = 2; i <= n; i++)
  95.     {
  96.         ll hsh = get_hash(i - 1, i);
  97.         mp[hsh]++;
  98.         mx_cnt = max(mx_cnt, mp[hsh]);
  99.     }
  100.     cout << mx_cnt, el;
  101.     if (mx_cnt == 0)
  102.         return 0;
  103.     mx_len = bs(1, n);
  104.     mp.clear();
  105.     for (int i = 1; i <= n - mx_len + 1; i++)
  106.     {
  107. //        cout << mx.fi << ' ' << mx.se, el;
  108. //        for (int j = mx.se; j <= mx.se + mx_len - 1; j++)
  109. //            cout << s[j];
  110. //        el;
  111.         mp[get_hash(i, i + mx_len - 1)]++;
  112.         int x = mp[get_hash(i, i + mx_len - 1)];
  113.         if (mx.fi < x)
  114.             mx = {x, i};
  115.         else if (mx.fi == x && cmp(i, mx.se))
  116.             mx.se = i;
  117. //        cout << mx.fi << ' ' << mx.se, el;
  118. //        for (int j = mx.se; j <= mx.se + mx_len - 1; j++)
  119. //            cout << s[j];
  120. //        el;
  121. //        el;
  122.     }
  123. //    mx_len = 2;
  124. //    string t = "";
  125. //    t += s[43];
  126. //    t += s[44];
  127. //    cout << t, el;
  128. //    t = "";
  129. //    t += s[22];
  130. //    t += s[23];
  131. //    cout << t, el;
  132. //    cout << cmp(204, 449), el;
  133.     for (int i = mx.se; i <= mx_len + mx.se - 1; i++)
  134.         cout << s[i];
  135. }
  136.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Rz0pfM
language:
C++14 (gcc 8.3)
created:
13 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!