daily pastebin goal
62%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 5e5 + 5;
  6.  
  7. string s;
  8. pair <int, int> a[N];
  9. long long pw[N], h[N], pr = 997, mod = 1e9 + 7;
  10. int n;
  11.  
  12. long long get(int l, int r){
  13.       long long hs = (h[r] - h[l - 1] + mod) % mod;
  14.       hs = (hs * pw[N - l]) % mod;
  15.       return hs;
  16. }
  17.  
  18. bool ok(pair <int, int> a, pair <int, int> b){
  19.       if(get(a.first, a.second) == get(b.first, b.second)) return 1;
  20.       int lo = 0, hi = n - 1;
  21.       while(lo < hi){
  22.             int md = (lo + hi) >> 1;
  23.             if(get(a.first, a.first + md) == get(b.first, b.first + md))
  24.                   lo = md + 1;
  25.             else
  26.                   hi = md;
  27.       }
  28.       return s[a.first + lo] < s[b.first + lo];
  29. }
  30.  
  31. pair <int, int> fun(int l, int r){
  32.       if(l == r){
  33.             return a[l];
  34.       }
  35.       int m = (l + r) >> 1;
  36.       pair <int, int> r1 = fun(l, m);
  37.       pair <int, int> r2 = fun(m + 1, r);
  38.       if(ok(r1, r2))
  39.             return r1;
  40.       else
  41.             return r2;
  42. }
  43.  
  44. int main(){
  45.       pw[0] = pr;
  46.       for(int i = 1; i < N; i ++){
  47.             pw[i] = (pw[i - 1] * pr) % mod;
  48.       }
  49.  
  50.       cin >> s;
  51.  
  52.       n = s.size();
  53.       s = ' ' + s + s;
  54.  
  55.       for(int i = 1; i < s.size(); i ++){
  56.             h[i] = (h[i - 1] + (pw[i] * s[i]) % mod) % mod;
  57.       }
  58.  
  59.       for(int i = 1; i <= n; i++){
  60.             a[i] = {i, i + n - 1};
  61.       }
  62.  
  63.       pair <int, int> p = fun(1, n);
  64.       string ans;
  65.       for(int i = p.first; i <= p.second; i ++)
  66.             ans += s[i];
  67.  
  68.       cout << ans << endl;
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top