Advertisement
Josif_tepe

Untitled

Dec 28th, 2023
1,096
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. using namespace std;
  5. typedef long long ll;
  6. const int alphabet_size = 26;
  7. const int base = 53;
  8. const ll MOD = 922337186621;
  9. void rolling_hash(string & s, int window_size, string & pattern) {
  10.    
  11.     int n = (int) s.size();
  12.     vector<ll> powers(n + 1, 1);
  13.     for(int i = 1; i <= n; i++) {
  14.         powers[i] = (powers[i - 1] * alphabet_size) % MOD;
  15.     }
  16.     ll hash = 0;
  17.     ll res_hash = 0;
  18.     set<pair<ll, ll> > st;
  19.     for(int i = 0; i < window_size; i++) {
  20.         res_hash = (res_hash * alphabet_size + pattern[i]) % MOD;
  21.     }
  22.     for(int i = 0; i < window_size; i++) {
  23.         hash = (hash * alphabet_size + s[i]) % MOD;
  24.     }
  25.     int res  =0 ;
  26.     if(hash == res_hash) {
  27.         bool ok = true;
  28.         for(int j = 0; j < window_size; j++) {
  29.             if(pattern[j] != s[j]) {
  30.                 ok = false;
  31.                 break;
  32.             }
  33.         }
  34.         if(ok) {
  35.             cout << 0 << endl;
  36.         }
  37.     }
  38.     for(int i = 1; i <= n - window_size; i++) {
  39.         hash = (hash - powers[window_size - 1] * s[i - 1]);
  40.         while (hash < 0) {
  41.             hash += MOD;
  42.         }
  43.         hash %= MOD;
  44.        
  45.         hash = (hash * alphabet_size + s[i + window_size - 1]) % MOD;
  46.         if(hash == res_hash) {
  47.             bool ok = true;
  48.             for(int j = 0; j < window_size; j++) {
  49.                 if(pattern[j] != s[i + j]) {
  50.                     ok = false;
  51.                     break;
  52.                 }
  53.             }
  54.             if(ok) {
  55.                 cout << i << endl;
  56.             }
  57.         }
  58.     }
  59.    
  60. }
  61. int main() {
  62.     ios_base::sync_with_stdio(false);
  63.     int win_size;
  64.     string text, pattern;
  65.    
  66.     while(cin >> win_size >> pattern >> text) {
  67.         rolling_hash(text, win_size, pattern);
  68.     }
  69.    return 0;
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement