Advertisement
StoneHaos

mod_n3_v18

Jan 26th, 2022
792
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  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 s, string t) {
  39.     // s = t
  40.     // t = p
  41.     int n = s.size();
  42.     int m = t.size();
  43.     int hashs = hashgen(s, 0, m, MOD);
  44.     int hasht = hashgen(t, 0, m, MOD);
  45.     for (int i = 0; i <= n - m; ++ i) {
  46.         if (hashs == hasht) {
  47.             int j = 0;
  48.             for (; j < m && t[j] == s[i + j]; ++ j);
  49.             if (j == m)
  50.                 return i;
  51.         }
  52.         if (i < n - m)
  53.             hashs = rehash(s, hashs, i, i + m, MOD);
  54.     }
  55.     return -1;
  56. }
  57.  
  58. int BM(string s, string t) {
  59.     vector<int> v;
  60.     for (int i = 0; i <= s.size() - t.size(); ++ i)
  61.         if (s[i] == t[0])
  62.             v.push_back(i);
  63.     for (int i = 0; i < v.size(); ++ i) {
  64.         int j = t.size() - 1;
  65.         for (; j >= 0; -- j) {
  66.             if (s[v[i] + j] != t[j]) break;
  67.         }
  68.         if (j == -1) return v[i];
  69.     }
  70.     return -1;
  71. }
  72.  
  73. int main() {
  74.     string s, t;
  75.     cin >> s >> t;
  76.     cout << BM(s, t) << endl;
  77.     cout << RB(s, t) << endl;
  78.     return 0;
  79. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement