Advertisement
StoneHaos

3

Jan 23rd, 2022
873
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <math.h>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 70000;
  8.  
  9. int powmod(int n, int p, int q) {
  10.     if (p == 0)
  11.         return 1;
  12.     return (powmod(n, p - 1, q) * n) % q;
  13. }
  14.  
  15. int hashgen(string s, int a, int b, int q) {
  16.     int x = 2;
  17.     int res = 0;
  18.     int n = b - a;
  19.     for (int i = 0; i < n; ++ i) {
  20.         res = ((res % q) + ((s[a + i] % q) * ((powmod(x, n - i - 1, q) % q)) % q)) % q;
  21.     }
  22.     return res;
  23.  
  24. }
  25.  
  26. int rehash(string s, int oldhash, int oldc, int newc, int q) {
  27.     int x = 2;
  28.     int step = newc - oldc - 1;
  29.     int newhash = oldhash;
  30.     int d1 = ((s[oldc] % q) * powmod(x, step, q)) % q;
  31.     while (newhash < d1) newhash += q;
  32.     newhash = (newhash - d1) % q;
  33.     newhash = (newhash * (x % q)) % q;
  34.     newhash = (newhash + (s[newc] % q)) % q;
  35.     return newhash;
  36. }
  37.  
  38. int RB(string p, string t) {
  39.     int n = t.size();
  40.     int m = p.size();
  41.     int hashp = hashgen(p, 0, m, MOD);
  42.     int hasht = hashgen(t, 0, m, MOD);
  43.     for (int i = 0; i <= n - m; ++ i) {
  44.         //printf("i = %d\nhashp = %d\nhasht = %d\n\n", i, hashp, hasht);
  45.         if (hasht == hashp) {
  46.             int j = 0;
  47.             for (; j < m && p[j] == t[i + j]; ++ j);
  48.             if (j == m)
  49.                 return i;
  50.         }
  51.         if (i < n - m)
  52.             hasht = rehash(t, hasht, i, i + m, MOD);
  53.     }
  54.     return -1;
  55. }
  56.  
  57. int KMP(string p, string t) {
  58.     int n = t.size();
  59.     int m = p.size();
  60.     int *dp = new int[m];
  61.     for (int i = 0; i < m; ++ i)
  62.         dp[i] = 0;
  63.     int j = 0;
  64.     for (int i = 1; i < m; i++) {
  65.         while (j > 0 && p[j] != p[i])
  66.             j = dp[j - 1];
  67.         if (p[j] == p[i])
  68.             j++;
  69.         dp[i] = j;
  70.     }
  71.  
  72.     int res = -1;
  73.     j = 0;
  74.     for (int i = 0; i < n; ++ i) {
  75.         while (j > 0 && p[j] != t[i])
  76.             j = dp[j - 1];
  77.         if (p[j] == t[i])
  78.             j++;
  79.         if (j == m) {
  80.             res = i - j + 1;
  81.             break;
  82.         }
  83.     }
  84.     delete [] dp;
  85.     return res;
  86. }
  87.  
  88. int main(void) {
  89.     string s, t;
  90.     cin >> s >> t;
  91.     int rb = RB(t, s);
  92.     int kmp = KMP(t, s);
  93.     cout << "Rabin-Karp: " << rb << endl;
  94.     cout << "KMP: " << kmp << endl;
  95.     return 0;
  96.  
  97. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement