Advertisement
milon34

two string are equal or not using (single hashing and double Hashing)

Feb 22nd, 2023 (edited)
37
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long int
  5. const int mx = 1e5 + 5;
  6. int p = 31, MOD = 1e9 + 7;
  7. int pw[mx];
  8.  
  9. void pw_cal() {
  10.     pw[0] = 1;
  11.     for (int i = 1; i <= mx; i++) {
  12.         pw[i] = (int) (1LL * pw[i - 1] * p) % MOD;
  13.     }
  14. }
  15.  
  16. int getHash(string s) {
  17.     int res = 0;
  18.     for (int i = 0; i < s.size(); i++) {
  19.         res += 1LL * (s[i] - 'a' + 1) * pw[i] % MOD;
  20.     }
  21.     return res;
  22. }
  23.  
  24. int main() {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(0);
  27.     pw_cal();
  28.     string s1, s2;
  29.     cin >> s1 >> s2;
  30.     cout << getHash(s1) << " " << getHash(s2) << endl;
  31.     return 0;
  32. }
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40. #include <bits/stdc++.h>
  41.  
  42. using namespace std;
  43. #define ll long long int
  44. const int mx = 1e5 + 5;
  45. int p1 = 31, p2 = 37, MOD = 1e9 + 9;
  46. int pw1[mx + 5], pw2[mx + 5];
  47.  
  48. void pw_cal() {
  49.     pw1[0] = 1;
  50.     for (int i = 1; i <= mx; i++) {
  51.         pw1[i] = (int) (1LL * pw1[i - 1] * p1) % MOD;
  52.     }
  53.     pw2[0] = 1;
  54.     for (int i = 1; i <= mx; i++) {
  55.         pw2[i] = (int) (1LL * pw2[i - 1] * p2) % MOD;
  56.     }
  57. }
  58.  
  59. pair<int, int> getHash(string s) {
  60.     int res1 = 0;
  61.     for (int i = 0; i < s.size(); i++) {
  62.         res1 += 1LL * (s[i] - 'a' + 1) * pw1[i] % MOD;
  63.         res1%=MOD;
  64.     }
  65.     int res2 = 0;
  66.     for (int i = 0; i < s.size(); i++) {
  67.         res2 += 1LL * (s[i] - 'a' + 1) * pw2[i] % MOD;
  68.         res2%=MOD:
  69.     }
  70.     return {res1, res2};
  71. }
  72.  
  73. int main() {
  74.     ios_base::sync_with_stdio(false);
  75.     cin.tie(0);
  76.     pw_cal();
  77.     string s1, s2;
  78.     cin >> s1 >> s2;
  79.     cout << (getHash(s1) == getHash(s2)) << endl;
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement