fork(9) download
copy 
  1. /*
  2.     Problem "202. Searching of asubstring" from acmp.ru
  3.     
  4.     Title: Searching of a substring
  5.  
  6. 	(Time limit: 0,5 sec. Memory limit: 16 MB Difficulty: 38%)
  7.  
  8. 	Find all occurrences of the string T in the string S.
  9.  
  10. 	Input:
  11.  
  12. 	The first line of the input file INPUT.TXT contains the string S, the second 
  13. 	line contains the string T. Both lines consist only of English letters. The 
  14. 	lengths of the lines can be in the range from 1 to 50 000 inclusive.
  15.  
  16. 	Output:
  17.  
  18. 	The output file OUTPUT.TXT needs to output all positions of the occurrence 
  19. 	of the string T in the string S in ascending order. The numbering of line 
  20. 	items starts from zero.
  21.     
  22.     Solution: polynomial hash, O(n)
  23. */
  24.  
  25. #include <stdio.h>
  26. #include <cassert>
  27. #include <algorithm>
  28. #include <vector>
  29. #include <random>
  30. #include <chrono>
  31. #include <string>
  32.  
  33. typedef unsigned long long ull;
  34.  
  35. // Generate random base in (before, after) open interval:
  36. int gen_base(const int before, const int after) {
  37.     auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
  38.     std::mt19937 mt_rand(seed);
  39.     int base = std::uniform_int_distribution<int>(before+1, after)(mt_rand);
  40.     return base % 2 == 0 ? base-1 : base;
  41. }
  42.  
  43. struct PolyHash {
  44.     // -------- Static variables --------
  45.     static const int mod = (int)1e9+123; // prime mod of polynomial hashing
  46.     static std::vector<int> pow1;        // powers of base modulo mod
  47.     static std::vector<ull> pow2;        // powers of base modulo 2^64
  48.     static int base;                     // base (point of hashing)
  49.  
  50.     // --------- Static functons --------
  51.     static inline int diff(int a, int b) { 
  52.     	// Diff between `a` and `b` modulo mod (0 <= a < mod, 0 <= b < mod)
  53.         return (a -= b) < 0 ? a + mod : a;
  54.     }
  55.  
  56.     // -------------- Variables of class -------------
  57.     std::vector<int> pref1; // Hash on prefix modulo mod
  58.     std::vector<ull> pref2; // Hash on prefix modulo 2^64
  59.  
  60.     // Cunstructor from string:
  61.     PolyHash(const std::string& s)
  62.         : pref1(s.size()+1u, 0)
  63.         , pref2(s.size()+1u, 0)
  64.     {
  65.         assert(base < mod);
  66.         const int n = s.size(); // Firstly calculated needed power of base:
  67.         while ((int)pow1.size() <= n) {
  68.             pow1.push_back(1LL * pow1.back() * base % mod);
  69.             pow2.push_back(pow2.back() * base);
  70.         }
  71.         for (int i = 0; i < n; ++i) { // Fill arrays with polynomial hashes on prefix
  72.             assert(base > s[i]);
  73.             pref1[i+1] = (pref1[i] + 1LL * s[i] * pow1[i]) % mod;
  74.             pref2[i+1] = pref2[i] + s[i] * pow2[i];
  75.         }
  76.     }
  77.  
  78.     // Polynomial hash of subsequence [pos, pos+len)
  79.     // If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
  80.     inline std::pair<int, ull> operator()(const int pos, const int len, const int mxPow = 0) const {
  81.         int hash1 = pref1[pos+len] - pref1[pos];
  82.         ull hash2 = pref2[pos+len] - pref2[pos];
  83.         if (hash1 < 0) hash1 += mod;
  84.         if (mxPow != 0) {
  85.             hash1 = 1LL * hash1 * pow1[mxPow-(pos+len-1)] % mod;
  86.             hash2 *= pow2[mxPow-(pos+len-1)];
  87.         }
  88.         return std::make_pair(hash1, hash2);
  89.     }
  90. };
  91.  
  92. // Init static variables of PolyHash class:
  93. int PolyHash::base((int)1e9+7);    
  94. std::vector<int> PolyHash::pow1{1};
  95. std::vector<ull> PolyHash::pow2{1};
  96.  
  97. int main() {
  98.     // Input:
  99.     char buf[1+100000];
  100.     scanf("%100000s", buf);
  101.     std::string a(buf);
  102.     scanf("%100000s", buf);
  103.     std::string b(buf);
  104.  
  105.     // Calculate max needed power:
  106.     const int mxPow = std::max((int)a.size(), (int)b.size());
  107.  
  108.     // Gen random base of hashing:
  109.     PolyHash::base = gen_base(256, PolyHash::mod);
  110.  
  111.     // Create hashing objects of strings `a` and `b`:
  112.     PolyHash hash_a(a), hash_b(b);
  113.  
  114.     // Copy needed hash from all string b:
  115.     const auto need = hash_b(0, (int)b.size(), mxPow);
  116.  
  117.     // Iterate over subsequences of string `a` neede length and compare hash with hash of string b:
  118.     for (int i = 0; i + (int)b.size() <= (int)a.size(); ++i) {
  119.         if (hash_a(i, b.size(), mxPow) == need) {
  120.             printf("%d ", i);
  121.         }
  122.     }
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0s 4448KB
comments (?)
stdin
copy 
ababbababa
aba
stdout
copy 
0 5 7
https://ideone.com/8fDG3W
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!