fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. using ll = long long;
  6. #define xx first
  7. #define yy second
  8. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  9.  
  10. ll modpow(ll a, ll b, ll mod) {
  11.     ll res = 1;
  12.     while (b > 0) {
  13.         if (b & 1) res = res * a % mod;
  14.         a = a * a % mod;
  15.         b >>= 1;
  16.     }
  17.     return (res + mod) % mod;
  18. }
  19. bool isPrime(ll n) {
  20.     if (n < 2) return false;
  21.     if (n == 2 || n == 3) return true;
  22.     if (n % 2 == 0 || n % 3 == 0) return false;
  23.     for (ll i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false;
  24.     return true;
  25. }
  26. ll mod1 = 127657753, mod2 = 987654319, p1 = 31, p2 = 37;
  27. ll invp1 = modpow(p1, mod1 - 2, mod1), invp2 = modpow(p2, mod2 - 2, mod2);
  28. void randomize() { // Randomize the mod and base
  29.     mod1 = rnd() % 100000000 + 900000000, mod2 = rnd() % 100000000 + 900000000;
  30.     while (!isPrime(mod1)) mod1++;        
  31.     while (!isPrime(mod2) || mod1 == mod2) mod2++;
  32.     p1 = rnd() % 100 + 31, p2 = rnd() % 100 + 37;
  33.     while (!isPrime(p1)) p1++;
  34.     while (!isPrime(p2) || p1 == p2) p2++;
  35.     invp1 = modpow(p1, mod1 - 2, mod1), invp2 = modpow(p2, mod2 - 2, mod2);
  36. }
  37. struct Hash {
  38.     string s;
  39.     int n = 0;
  40.     vector<pair<ll, ll>> sHash, pPow, invpPow;
  41.     void setVal(string& S) { // Set the string
  42.         s = S, n = S.size();
  43.     }
  44.     void genP() { // Generate powers of p and invp for faster queries
  45.         pPow.resize(n + 1, {1, 1});
  46.         invpPow.resize(n + 1, {1, 1});
  47.         for (int i = 1; i <= n; i++) {
  48.             pPow[i].xx = pPow[i - 1].xx * p1 % mod1;
  49.             pPow[i].yy = pPow[i - 1].yy * p2 % mod2;
  50.             invpPow[i].xx = invpPow[i - 1].xx * invp1 % mod1;
  51.             invpPow[i].yy = invpPow[i - 1].yy * invp2 % mod2;
  52.         }
  53.     }
  54.     void genHash() { // 0-indexed
  55.         sHash.resize(n + 1, {0, 0});
  56.         for (int i = 0; i < n; i++) {
  57.             sHash[i + 1].xx = (sHash[i].xx + (s[i] - 'a' + 1) * pPow[i].xx) % mod1;
  58.             sHash[i + 1].yy = (sHash[i].yy + (s[i] - 'a' + 1) * pPow[i].yy) % mod2;
  59.         }
  60.     }
  61.     pair<ll, ll> getHash(int l, int r) { // 0-indexed
  62.         ll h1 = (sHash[r + 1].xx - sHash[l].xx + mod1) % mod1 * invpPow[l].xx % mod1;
  63.         ll h2 = (sHash[r + 1].yy - sHash[l].yy + mod2) % mod2 * invpPow[l].yy % mod2;
  64.         return {h1, h2};
  65.     }
  66.     pair<ll, ll> getHash() { // Get the hash of the whole string
  67.         return getHash(0, n - 1);
  68.     }
  69.     void doAll(string& S) {
  70.         setVal(S), genP(), genHash();
  71.     }
  72. };
  73.  
  74. signed main(){
  75.     ios_base::sync_with_stdio(false);
  76.     cin.tie(NULL);
  77.     cout.tie(NULL);
  78.     string s;
  79.     cin >> s;
  80.     int n = s.size();
  81.     s += s;
  82.     Hash h;
  83.     h.doAll(s);
  84.     int mx = 0;
  85.     for(int i = 1; i < n; i++){
  86.         int lo = 0, hi = n - 1, res = -1;
  87.         while(lo <= hi){
  88.             int mid = (lo + hi) / 2;
  89.             if(h.getHash(0 + mx, mid + mx) == h.getHash(0 + i, mid + i)) lo = mid + 1;
  90.             else {
  91.                 hi = mid - 1;
  92.                 res = mid;
  93.             }
  94.         }
  95.         if(res != -1 and s[0 + mx + res] > s[0 + i + res]) mx = i;
  96.     }
  97.     cout << s.substr(mx, n - mx);
  98.     cout << s.substr(0, mx);
  99.     return 0;
  100. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jBIcA1
language:
C++ (gcc 8.3)
created:
34 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!