fork(11) download
copy 
  1. /*
  2.     Problem "1156. Minimal shift" from acmp.ru
  3.     
  4.     Solution: polynomial hash, binary search, linear search of min O(n log(n))
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <cassert>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <random>
  12. #include <chrono>
  13. #include <string>
  14.  
  15. typedef unsigned long long ull;
  16.  
  17. // Generate random base in (before, after) open interval:
  18. int gen_base(const int before, const int after) {
  19.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  20.     std::mt19937 mt_rand(seed);
  21.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  22.     return base % 2 == 0 ? base-1 : base;
  23. }
  24.  
  25. struct PolyHash {
  26.     // -------- Static variables --------
  27.     static const int mod = (int)1e9+123; // prime mod of polynomial hashing
  28.     static std::vector<int> pow1;        // powers of base modulo mod
  29.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  30.     static int base;                     // base (point of hashing)
  31.  
  32.     // --------- Static functons --------
  33.     static inline int diff(int a, int b) { 
  34.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  35.         return (a -= b) < 0 ? a + mod : a;
  36.     }
  37.  
  38.     // -------------- Variables of class -------------
  39.     std::vector<int> pref1; // Hash on prefix modulo mod
  40.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  41.  
  42.     // Cunstructor from string:
  43.     PolyHash(const std::string& s)
  44.         : pref1(s.size()+1u, 0)
  45.         , pref2(s.size()+1u, 0)
  46.     {
  47.         assert(base < mod);
  48.         const int n = s.size(); // Firstly calculated needed power of base:
  49.         while ((int)pow1.size() <= n) {
  50.             pow1.push_back(1LL * pow1.back() * base % mod);
  51.             pow2.push_back(pow2.back() * base);
  52.         }
  53.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  54.             assert(base > s[i]);
  55.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  56.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  57.         }
  58.     }
  59.  
  60.     // Polynomial hash of subsequence [pos, pos+len)
  61.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  62.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  63.         int hash1 = pref1[pos+len] - pref1[pos];
  64.         ull hash2 = pref2[pos+len] - pref2[pos];
  65.         if (hash1 < 0) hash1 += mod;
  66.         if (mxPow != 0) {
  67.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  68.             hash2 *= pow2[mxPow-(pos+len-1)];
  69.         }
  70.         return std::make_pair(hash1, hash2);
  71.     }
  72. };
  73.  
  74. // Init static variables of PolyHash class:
  75. int PolyHash::base((int)1e9+7);    
  76. std::vector<int> PolyHash::pow1{1};
  77. std::vector<ull> PolyHash::pow2{1};
  78.  
  79. int main() {
  80.     // Input:
  81.     char buf[1+100000];
  82.     scanf("%100000s", buf);
  83.     std::string a(buf);
  84.     a += a; // duplicate
  85.  
  86.     // Len of string:
  87.     const int n = (int)a.size() / 2;
  88.  
  89.     // Max needed power:
  90.     const int mxPow = 2 * n;
  91.  
  92.     // Gen random base:
  93.     PolyHash::base = gen_base(256, PolyHash::mod);
  94.  
  95.     // Create hashing object:
  96.     PolyHash hash(a);
  97.  
  98.     // Put all start positions in vector:
  99.     std::vector<int> pos;
  100.     for (int i = 0; i < n; ++i) {
  101.         pos.push_back(i);
  102.     }
  103.  
  104.     // Linear search of min algorithm:
  105.     auto p = *std::min_element(pos.begin(), pos.end(), [&](const int p1, const int p2) {
  106.         // Binary search by equal subsequences length:
  107.         int low = 0, high = n+1;
  108.         while (high - low > 1) {
  109.             int mid = (low + high) / 2;
  110.             if (hash(p1, mid, mxPow) == hash(p2, mid, mxPow)) {
  111.                 low = mid;
  112.             } else {
  113.                 high = mid;
  114.             }
  115.         }
  116.         return low < n && a[p1+low] < a[p2+low];
  117.     });
  118.  
  119.     // Output answer:
  120.     printf("%s", a.substr(p, n).c_str());
  121.     return 0;
  122. }
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
program
stdout
copy 
amprogr
https://ideone.com/kTNj4P
language:
C++14 (gcc 8.3)
created:
6 years 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!