fork(1) download
copy 
  1. /*
  2.     Problem "829. Strings - 3" from acmp.ru
  3.     
  4.     Title: Strings - 3
  5.  
  6.     (Time limit: 2 sec. Memory limit: 16 MB Difficulty: 80%)
  7.  
  8.     A cyclic shift of a string s is the string: 
  9.     
  10.     	s_{k}s_{k+1}s_{k+2} ... s_{|s|} s_{1}s_{2} ... s_{k-1} 
  11.  
  12. 	for some k, where |s| is the length of the string s. A substring of the 
  13. 	string s is the string s_{i}s_{i+1} ... s_{j-1}s_{j} for some i and j. 
  14.  
  15. 	Given two strings a and b. Output the number of substrings of string a, 
  16. 	which are cyclic shifts of string b.
  17.  
  18.     Input:
  19.  
  20.     The first line of the input file INPUT.TXT contains the string a 
  21.     (1 \le |a| \le 10^5). The second line of the input file contains the string 
  22.     b (1 \le |b| \le |a|). Both strings consist only of English alphabet 
  23.     and digits.
  24.  
  25.     Output:
  26.  
  27.     In output file OUTPUT.TXT print one integer - the answer to the problem.
  28.     
  29.     Solution: polynomial hashes, sort, binary search, O(n log(n))
  30. */
  31.  
  32. #include <stdio.h>
  33. #include <cassert>
  34. #include <algorithm>
  35. #include <vector>
  36. #include <random>
  37. #include <chrono>
  38. #include <string>
  39.  
  40. typedef unsigned long long ull;
  41.  
  42. // Generate random base in (before, after) open interval:
  43. int gen_base(const int before, const int after) {
  44.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  45.     std::mt19937 mt_rand(seed);
  46.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  47.     return base % 2 == 0 ? base-1 : base;
  48. }
  49.  
  50. struct PolyHash {
  51.     // -------- Static variables --------
  52.     static const int mod = (int)1e9+123; // prime mod of polynomial hashing
  53.     static std::vector<int> pow1;        // powers of base modulo mod
  54.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  55.     static int base;                     // base (point of hashing)
  56.  
  57.     // --------- Static functons --------
  58.     static inline int diff(int a, int b) { 
  59.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  60.         return (a -= b) < 0 ? a + mod : a;
  61.     }
  62.  
  63.     // -------------- Variables of class -------------
  64.     std::vector<int> pref1; // Hash on prefix modulo mod
  65.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  66.  
  67.     // Cunstructor from string:
  68.     PolyHash(const std::string& s)
  69.         : pref1(s.size()+1u, 0)
  70.         , pref2(s.size()+1u, 0)
  71.     {
  72.         assert(base < mod);
  73.         const int n = s.size(); // Firstly calculated needed power of base:
  74.         while ((int)pow1.size() <= n) {
  75.             pow1.push_back(1LL * pow1.back() * base % mod);
  76.             pow2.push_back(pow2.back() * base);
  77.         }
  78.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  79.             assert(base > s[i]);
  80.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  81.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  82.         }
  83.     }
  84.  
  85.     // Polynomial hash of subsequence [pos, pos+len)
  86.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  87.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  88.         int hash1 = pref1[pos+len] - pref1[pos];
  89.         ull hash2 = pref2[pos+len] - pref2[pos];
  90.         if (hash1 < 0) hash1 += mod;
  91.         if (mxPow != 0) {
  92.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  93.             hash2 *= pow2[mxPow-(pos+len-1)];
  94.         }
  95.         return std::make_pair(hash1, hash2);
  96.     }
  97. };
  98.  
  99. // Init static variables of PolyHash class:
  100. int PolyHash::base((int)1e9+7);    
  101. std::vector<int> PolyHash::pow1{1};
  102. std::vector<ull> PolyHash::pow2{1};
  103.  
  104. int main() {
  105.     // Input:
  106.     char buf[1+100000];
  107.     scanf("%100000s", buf);
  108.     std::string a(buf);
  109.     scanf("%100000s", buf);
  110.     std::string b(buf);
  111.  
  112.     // Get max needed power of base:
  113.     const int mxPow = std::max((int)a.size(), (int)b.size() * 2);
  114.  
  115.     // Gen random base of polynomial hashing:
  116.     PolyHash::base = gen_base(256, PolyHash::mod);
  117.  
  118.     // Create hash ibject of strings a and b:
  119.     PolyHash hash_a(a), hash_b(b+b);
  120.  
  121.     // Put all hashes of substrings of string b fixed length and sort:
  122.     std::vector<std::pair<int, ull>> hashes;
  123.     for (int i = 0; i  < (int)b.size(); ++i) {
  124.         hashes.push_back(hash_b(i, b.size(), mxPow));
  125.     }
  126.     std::sort(hashes.begin(), hashes.end());
  127.  
  128.     // Iterate over substrings of string a ansd search hash with fix length:
  129.     int answ = 0;
  130.     for (int i = 0; i + (int)b.size() <= (int)a.size(); ++i) {
  131.         answ += std::binary_search(hashes.begin(), hashes.end(), hash_a(i, b.size(), mxPow));
  132.     }
  133.     // Output:
  134.     printf("%d", answ);
  135.  
  136.     return 0;
  137. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
aAaa8aaAa
aAa
stdout
copy 
4
https://ideone.com/zPTXUw
language:
C++14 (gcc 8.3)
created:
5 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!