Advertisement
StoneHaos

10

Nov 29th, 2021
516
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <math.h>
  3. #include <algorithm>
  4. #include <string>
  5.  
  6. using namespace std;
  7.  
  8. const int q = 65536;
  9.  
  10. int hashc(string s, int a, int b) {
  11.     int n = b - a;
  12.     int sum = 0;
  13.     for (int i = 0; i < n; ++ i) {
  14.         sum += s[a + i] * (int)pow(2, n - i - 1);
  15.     }
  16.     sum %= q;
  17.     return sum;
  18. }
  19.  
  20. int RABINKarp(string s, string t) {
  21.     int n = s.size();
  22.     int m = t.size();
  23.     int h = hashc(t, 0, m);
  24.     for (int i = 0; i < n - m + 1; ++ i) {
  25.         if (h == hashc(s, i, i + m)) {
  26.             bool eq = true;
  27.             for (int j = 0; j < m; ++ j)
  28.                 if (s[i + j] != t[j])
  29.                     eq = false;
  30.             if (eq) return i;
  31.         }
  32.     }
  33.     return -1;
  34. }
  35.  
  36. int main() {
  37.     string s, t;
  38.     cin >> s >> t;
  39.     cout << RABINKarp(s, t) << endl;
  40.     return 0;
  41. }
Advertisement
RAW Paste Data Copied
Advertisement