fork download
copy 
  1. /*
  2.     Problem "1158. Cyclic shifts" from acmp.ru
  3.  
  4. 	(Time limit: 5 sec. Memory limit: 16 MB Difficulty: 76%)
  5.  
  6. 	A cyclic shift of the string s is the string: 
  7.  
  8. 	    s_{k+1}s_{k+2} ... s_{n}s_{1}s_{2} ... s_{k} 
  9.  
  10. 	for some k (0 \le k < n), where n is the length of the string s.
  11.  
  12. 	For a given string, it is required to construct all cyclic shifts, arrange 
  13. 	them lexicographically, write out the last column, and find the position of 
  14. 	the original row in this list.
  15.  
  16. 	Input:
  17.  
  18. 	In the single line of the input file INPUT.TXT a string consisting of 
  19. 	characters with ASCII codes from 33 to 127. A string length does not 
  20. 	exceed 10^5.
  21.  
  22. 	Output:
  23.  
  24. 	In the first line of the output file OUTPUT.TXT, output the position number 
  25. 	of the given string in the sorted list of cyclic shifts. If there are 
  26. 	several such positions, then the position with the smallest number should 
  27. 	be printed. In the second line, output the last column of the sorted cyclic 
  28. 	shift table.
  29.  
  30. 	Example:
  31.  
  32. 	Firstly, we write out all 6 cyclic shifts of the string "abraka" and order 
  33. 	the resulting list lexicographically:
  34.  
  35. 	Original list:
  36.  
  37. 	abraka +
  38. 	brakaa
  39. 	rakaab
  40. 	akaabr
  41. 	kaabra
  42. 	aabrak
  43.  
  44. 	Sorted list:
  45.  
  46. 	aabrak	
  47. 	abraka +
  48. 	akaabr
  49. 	brakaa
  50. 	kaabra
  51. 	rakaab
  52.  
  53. 	Now we see that in the sorted list the original word is in the 2-nd 
  54. 	position, and the last column is the string "karaab".
  55.  
  56.     Solution: polynomial hash, binary search, sort, O(n log(n)^2)
  57. */
  58.  
  59. #include <stdio.h>
  60. #include <cassert>
  61. #include <algorithm>
  62. #include <vector>
  63. #include <random>
  64. #include <chrono>
  65. #include <string>
  66.  
  67. typedef unsigned long long ull;
  68.  
  69. // Generate random base in (before, after) open interval:
  70. int gen_base(const int before, const int after) {
  71.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  72.     std::mt19937 mt_rand(seed);
  73.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  74.     return base % 2 == 0 ? base-1 : base;
  75. }
  76.  
  77. struct PolyHash {
  78.     // -------- Static variables --------
  79.     static const int mod = (int)1e9+123; // prime mod of polynomial hashing
  80.     static std::vector<int> pow1;        // powers of base modulo mod
  81.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  82.     static int base;                     // base (point of hashing)
  83.  
  84.     // --------- Static functons --------
  85.     static inline int diff(int a, int b) { 
  86.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  87.         return (a -= b) < 0 ? a + mod : a;
  88.     }
  89.  
  90.     // -------------- Variables of class -------------
  91.     std::vector<int> pref1; // Hash on prefix modulo mod
  92.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  93.  
  94.     // Cunstructor from string:
  95.     PolyHash(const std::string& s)
  96.         : pref1(s.size()+1u, 0)
  97.         , pref2(s.size()+1u, 0)
  98.     {
  99.         assert(base < mod);
  100.         const int n = s.size(); // Firstly calculated needed power of base:
  101.         while ((int)pow1.size() <= n) {
  102.             pow1.push_back(1LL * pow1.back() * base % mod);
  103.             pow2.push_back(pow2.back() * base);
  104.         }
  105.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  106.             assert(base > s[i]);
  107.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  108.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  109.         }
  110.     }
  111.  
  112.     // Polynomial hash of subsequence [pos, pos+len)
  113.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  114.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  115.         int hash1 = pref1[pos+len] - pref1[pos];
  116.         ull hash2 = pref2[pos+len] - pref2[pos];
  117.         if (hash1 < 0) hash1 += mod;
  118.         if (mxPow != 0) {
  119.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  120.             hash2 *= pow2[mxPow-(pos+len-1)];
  121.         }
  122.         return std::make_pair(hash1, hash2);
  123.     }
  124. };
  125.  
  126. // Init static variables of PolyHash class:
  127. int PolyHash::base((int)1e9+7);    
  128. std::vector<int> PolyHash::pow1{1};
  129. std::vector<ull> PolyHash::pow2{1};
  130.  
  131. int main() {
  132.     // Inout:
  133.     char buf[1+100000];
  134.     scanf("%100000s", buf);
  135.     std::string a(buf);
  136.     a += a;
  137.  
  138.     // Length of string:
  139.     const int n = (int)a.size() / 2;
  140.  
  141.     // Calculate max neede power of base:
  142.     const int mxPow = 2 * n;
  143.  
  144.     // Init random base of hashing:
  145.     PolyHash::base = gen_base(256, PolyHash::mod);
  146.  
  147.     // Creare hashing object over string a:
  148.     PolyHash hash(a);
  149.  
  150.     // Put all starts positions in vector:
  151.     std::vector<int> pos;
  152.     for (int i = 0; i < n; ++i) {
  153.         pos.push_back(i);
  154.     }
  155.  
  156.     // Sort all items:
  157.     std::stable_sort(pos.begin(), pos.end(), [&](const int p1, const int p2) {
  158.         // Sinary search by the len of equal part:
  159.         int low = 0, high = n+1;
  160.         while (high - low > 1) {
  161.             int mid = (low + high) / 2;
  162.             if (hash(p1, mid, mxPow) == hash(p2, mid, mxPow)) {
  163.                 low = mid;
  164.             } else {
  165.                 high = mid;
  166.             }
  167.         }
  168.         return low < n && a[p1+low] < a[p2+low];
  169.     });
  170.  
  171.     // Output answer:
  172.     printf("%d\n", int(std::find(pos.begin(), pos.end(), 0)-pos.begin())+1);
  173.     std::string temp;
  174.     for (auto p : pos) {
  175.         temp.push_back(a[p+n-1]);
  176.     }
  177.     printf("%s", temp.c_str());
  178.     return 0;
  179. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
abraka
stdout
copy 
2
karaab
https://ideone.com/Ob8izE
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!