StoneHaos

3

Feb 18th, 2022 (edited)
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <math.h>
  5.  
  6. using namespace std;
  7.  
  8. const int MOD = 70000;
  9.  
  10. int BM(string s, string t) {
  11.     vector<int> v;
  12.     for (int i = 0; i <= s.size() - t.size(); ++ i)
  13.         if (s[i] == t[0])
  14.             v.push_back(i);
  15.     for (int i = 0; i < v.size(); ++ i) {
  16.         int j = t.size() - 1;
  17.         for (; j >= 0; -- j) {
  18.             if (s[v[i] + j] != t[j]) break;
  19.         }
  20.         if (j == -1) return v[i];
  21.     }
  22.     return -1;
  23. }
  24.  
  25. int KMP(string p, string t) {
  26.     int n = t.size();
  27.     int m = p.size();
  28.     int *dp = new int[m];
  29.     for (int i = 0; i < m; ++ i)
  30.         dp[i] = 0;
  31.     int j = 0;
  32.     for (int i = 1; i < m; i++) {
  33.         while (j > 0 && p[j] != p[i])
  34.             j = dp[j - 1];
  35.         if (p[j] == p[i])
  36.             j++;
  37.         dp[i] = j;
  38.     }
  39.  
  40.     int res = -1;
  41.     j = 0;
  42.     for (int i = 0; i < n; ++ i) {
  43.         while (j > 0 && p[j] != t[i])
  44.             j = dp[j - 1];
  45.         if (p[j] == t[i])
  46.             j++;
  47.         if (j == m) {
  48.             res = i - j + 1;
  49.             break;
  50.         }
  51.     }
  52.     delete [] dp;
  53.     return res;
  54. }
  55.  
  56. int main(void) {
  57.     string s, t;
  58.     cin >> s >> t;
  59.     int rb = BM(s, t);
  60.     int kmp = KMP(t, s);
  61.     cout << "Boyer-Mour: " << rb << endl;
  62.     cout << "KMP: " << kmp << endl;
  63.     return 0;
  64.  
  65. }
RAW Paste Data Copied