SHARE
TWEET

Untitled

a guest Nov 18th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. long long m = 10e9 + 7;
  7.  
  8. long long add(const long long& a, const long long& b) {
  9.     if (a + b > m) {
  10.         return a + b - m;
  11.     }
  12.     return a + b;
  13. }
  14.  
  15. long long mult(const long long& a, const long long& b) {
  16.     return(a * b) % m;
  17. }
  18.  
  19. long long sub(const long long& a, const long long& b) {
  20.     if (a - b < m) {
  21.         return a - b + m;
  22.     }
  23.     return a - b;
  24. }
  25.  
  26. int main() {
  27.     ifstream fin("input.txt");
  28.     ofstream fout("output.txt");
  29.     string str, str2;
  30.     long long hash2;
  31.     int p = 239;
  32.     fin >> str >> str2;
  33.     vector<long long>hash(str.size() + 1);
  34.     vector<long long>power(str.size() + 1);
  35.     power[0] = 1;
  36.     hash[0] = 0;
  37.     for (int i = 1; i < str.size() + 1; i++) {
  38.         power[i] = mult(power[i - 1] , p);
  39.         hash[i] = add(mult(hash[i - 1], p), str[i - 1]);
  40.     }
  41.     hash2 = str2[0];
  42.     for (int i = 1; i < str2.size(); i++) {
  43.         hash2 = add(mult(hash2, p), str2[i]);
  44.     }
  45.  
  46.     for (int i = str2.size(); i < hash.size(); ++i) {
  47.         if (sub(hash[i], mult(hash[i - str2.size()], power[str2.size()])) == hash2) {
  48.             fout << i - str2.size() + 1;
  49.         }
  50.     }
  51. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top