Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <string>
  4. #include <vector>
  5.  
  6. #define ull unsigned long long
  7.  
  8. using namespace std;
  9.  
  10. struct Hash {
  11.     vector<ull> hash;
  12.     vector<ull> pow;
  13.  
  14.     void build_hash(string& s, ull radix) {
  15.         hash.resize(s.size());
  16.         pow.resize(s.size());
  17.  
  18.         pow[0] = 1;
  19.         hash[0] = s[0] - 'a' + 1;
  20.         for (int i = 1; i < s.size(); ++i) {
  21.             pow[i] = pow[i - 1] * radix;
  22.             hash[i] = hash[i - 1] * radix + (s[i] - 'a' + 1);
  23.         }
  24.     }
  25.  
  26.     ull get_hash(int l, int r) {
  27.         if (l == 0) {
  28.             return hash[r];
  29.         }
  30.         return hash[r] - hash[l - 1] * pow[r - l + 1];
  31.     }
  32. };
  33.  
  34. int main() {
  35.     string s, substring;
  36.     int n;
  37.     set<int> positions;
  38.     Hash h1, h2;
  39.  
  40.     cin >> s >> substring;
  41.     n = substring.size() - 1;
  42.  
  43.     h1.build_hash(s, 29);
  44.     h2.build_hash(substring, 29);
  45.  
  46.     for (int i = 0; i < s.size() - n; ++i) {
  47.         if (h2.get_hash(0, n) == h1.get_hash(i, i + n)) {
  48.             positions.insert(i);
  49.         }
  50.     }
  51.  
  52.     cout << positions.size() << '\n';
  53.     for (auto & pos : positions) {
  54.         cout << pos << ' ';
  55.     }
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement