fork download
copy 
  1. /*
  2.     Problem "886. Suffixes" from acmp.ru
  3.  
  4.     Let the string be a sequence of small letters of the English alphabet. For 
  5.     example, empty sequence "" is a string, the word "aabaf" or an infinite 
  6.     sequence of letters "a" are string too.
  7.  
  8.     The i-th suffix S_i of the string S is the string S from which the first i 
  9.     letters are cut: so, for the string S = "aabaf" the suffixes will be:
  10.  
  11.     S_0 = “aabaf”
  12.  
  13.     S_1 = “abaf”
  14.  
  15.     S_2 = “baf”
  16.  
  17.     S_3 = “af”
  18.  
  19.     S_4 = “f”
  20.  
  21.     S_5 = S_6 = S_7 = . . . = “”
  22.  
  23.     The suffixes are defined for all i > 0.
  24.  
  25.     The cyclic extension S^* of a finite string S is a string obtained by 
  26.     duplicating it to itself an infinite number of times. So,
  27.  
  28.     S^* = S_0^* = “aabafaabafaa...”
  29.  
  30.     S_1^* = “abafabafabaf...”
  31.  
  32.     S_2^* = “bafbafbafbaf...”
  33.  
  34.     S_3^* = “afafafafafaf...”
  35.  
  36.     S_4^* = “ffffffffffff...”
  37.  
  38.     S_5^* = S_6^* = S_7^*= . . . = “”
  39.  
  40.     For a given string S, find out how many of its suffixes S_i have the same 
  41.     cyclic extension as the string S itself, that is, the number of different i 
  42.     such that S^* = S_i^*.
  43.  
  44.     Input:
  45.  
  46.     The input file INPUT.TXT contains a string S consisting of at least one and 
  47.     not more than 100 000 small English letters.
  48.  
  49.     Output:
  50.  
  51.     In the output file OUTPUT.TXT output the number of suffixes of the string S 
  52.     having the same cyclic extension as itself.
  53.  
  54.     
  55.     Solution: polynomial hashes, geometric progression, O(n log(n))
  56. */
  57.  
  58. #include <stdio.h>
  59. #include <cassert>
  60. #include <algorithm>
  61. #include <vector>
  62. #include <random>
  63. #include <chrono>
  64. #include <string>
  65.  
  66. typedef unsigned long long ull;
  67.  
  68. // Generate random base in (before, after) open interval:
  69. int gen_base(const int before, const int after) {
  70.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  71.     std::mt19937 mt_rand(seed);
  72.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  73.     return base % 2 == 0 ? base-1 : base;
  74. }
  75.  
  76. struct PolyHash {
  77.     // -------- Static variables --------
  78.     static const int mod = (int)1e9+123; // prime mod of polynomial hashing
  79.     static std::vector<int> pow1;        // powers of base modulo mod
  80.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  81.     static int base;                     // base (point of hashing)
  82.  
  83.     // --------- Static functons --------
  84.     static inline int diff(int a, int b) { 
  85.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  86.         return (a -= b) < 0 ? a + mod : a;
  87.     }
  88.  
  89.     // -------------- Variables of class -------------
  90.     std::vector<int> pref1; // Hash on prefix modulo mod
  91.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  92.  
  93.     // Cunstructor from string:
  94.     PolyHash(const std::string& s)
  95.         : pref1(s.size()+1u, 0)
  96.         , pref2(s.size()+1u, 0)
  97.     {
  98.         assert(base < mod);
  99.         const int n = s.size(); // Firstly calculated needed power of base:
  100.         while ((int)pow1.size() <= n) {
  101.             pow1.push_back(1LL * pow1.back() * base % mod);
  102.             pow2.push_back(pow2.back() * base);
  103.         }
  104.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  105.             assert(base > s[i]);
  106.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  107.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  108.         }
  109.     }
  110.  
  111.     // Polynomial hash of subsequence [pos, pos+len)
  112.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  113.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  114.         int hash1 = pref1[pos+len] - pref1[pos];
  115.         ull hash2 = pref2[pos+len] - pref2[pos];
  116.         if (hash1 < 0) hash1 += mod;
  117.         if (mxPow != 0) {
  118.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  119.             hash2 *= pow2[mxPow-(pos+len-1)];
  120.         }
  121.         return std::make_pair(hash1, hash2);
  122.     }
  123. };
  124.  
  125. // Init static variables of PolyHash class:
  126. int PolyHash::base((int)1e9+7);    
  127. std::vector<int> PolyHash::pow1{1};
  128. std::vector<ull> PolyHash::pow2{1};
  129.  
  130. // Functions for calculating this sum: 1 + a + a^2 + ... + a^(k-1) by modulo
  131. // mod and 2^64 in O(log(k))
  132. int sum_int(int a, int k) {
  133.     if (k == 1) {
  134.         return 1;
  135.     } else if (k % 2 == 0) {
  136.         return (1LL + a) * sum_int(1LL * a * a % PolyHash::mod, k / 2) % PolyHash::mod;
  137.     } else {
  138.         return 1 + (a+1LL) * a % PolyHash::mod * sum_int(1LL * a * a % PolyHash::mod, k / 2) % PolyHash::mod;
  139.     }
  140. }
  141.  
  142. ull sum_ull(ull a, int k) {
  143.     if (k == 1) {
  144.         return 1;
  145.     } else if (k % 2 == 0) {
  146.         return (1 + a) * sum_ull(a * a, k / 2);
  147.     } else {
  148.         return 1 + a * sum_ull(a, k - 1);
  149.     }
  150. }
  151.  
  152. int main() {    
  153.     static char buf[1+100000];
  154.     scanf("%100000s", buf);
  155.     std::string a(buf);
  156.  
  157.     std::reverse(a.begin(), a.end()); // reverse
  158.  
  159.     // Gen random point of hashing:
  160.     PolyHash::base = gen_base(256, PolyHash::mod);
  161.  
  162.     // Construct hashes on prefixes of substring a:
  163.     PolyHash hash(a);
  164.  
  165.     // Length of string:
  166.     const int n = (int)a.size();
  167.  
  168.     int answ = 0;    
  169.     for (int len = 1; len <= n; ++len) {
  170.         // Get polynomial hash:
  171.         auto hash1 = hash(0, len); // on prefix a[0...len)
  172.         auto hash2 = hash(0, n);   // on prefix a[0...n)
  173.  
  174.         // Multiply on sum of geometry progression hash modulo mod:
  175.         hash1.first = 1LL * hash1.first * sum_int(PolyHash::pow1[len], n) % PolyHash::mod;
  176.         hash2.first = 1LL * hash2.first * sum_int(PolyHash::pow1[n], len) % PolyHash::mod;
  177.  
  178.         // Multiply on sum of geometry progression hash modulo 2^64:
  179.         hash1.second *= sum_ull(PolyHash::pow2[len], n);
  180.         hash2.second *= sum_ull(PolyHash::pow2[n], len);       
  181.  
  182.         // Compare hashes:
  183.         answ += (hash1 == hash2);
  184.     }
  185.     printf("%d", answ);
  186.  
  187.     return 0;
  188. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
qqqqqqq
stdout
copy 
7
https://ideone.com/abHJQZ
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!