fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. #define ll long long
  6. #define endl '\n'
  7. #define all(x) x.begin(), x.end()
  8. #define rall(x) x.rbegin(), x.rend()
  9. #define mem(a, b) memset(a, b, sizeof(a))
  10. #define read(x)        \
  11.     for (auto &it : x) \
  12.         cin >> it;
  13. #define write(x)      \
  14.     for (auto it : x) \
  15.         cout << it << " ";
  16. const int MOD = 1e9 + 7;
  17. const int N = 4e5 + 7;
  18. ll Bs1[] = {27407, 4629423, 1629007, 8629891, 4629421, 1627979, 8627573, 8627947, 87257};
  19. ll Bs2[] = {12345653, 28351, 45953, 75879031, 6389, 12349559, 9326651, 93255989, 2111};
  20. ll Md1[] = {1000001329, 1745005183, 1000002239, 1345005517, 200002577, 1000003559, 1000003397, 987001789, 1000004207};
  21. ll Md2[] = {1734557563, 1034558389, 1134559717, 1234555639, 1534556819, 1634555621, 1445003887, 1834567627, 1334558999};
  22. ll bs1, bs2, md1, md2;
  23. ll pow1[N], pow2[N];
  24. ll pre1[N], pre2[N];
  25. void pow_cal()
  26. {
  27.     pow1[0] = pow2[0] = 1;
  28.     for (int i = 1; i < N; i++)
  29.     {
  30.         pow1[i] = (pow1[i - 1] * bs1) % md1;
  31.         pow2[i] = (pow2[i - 1] * bs2) % md2;
  32.     }
  33. }
  34.  
  35. // build function for hash
  36. void build_hash(string &s)
  37. {
  38.     pre1[0] = 0, pre2[0] = 0;
  39.     for (int i = 1; i <= s.length(); i++)
  40.     {
  41.         ll x = s[i - 1] - 'a' + 1;
  42.         pre1[i] = ((pre1[i - 1] * bs1) % md1) + x;
  43.         pre1[i] %= md1;
  44.  
  45.         pre2[i] = ((pre2[i - 1] * bs2) % md2) + x;
  46.         pre2[i] %= md2;
  47.     }
  48. }
  49.  
  50. // function to get the hash value for substring l to r, here l, r is 1 based indexed
  51. pair<ll, ll> get_hash_value(ll l, ll r)
  52. {
  53.     if (l > r)
  54.         return {-1, -1};
  55.  
  56.     int hash1 = (pre1[r] - (pre1[l - 1] * pow1[r - l + 1])) % md1;
  57.     hash1 = (hash1 + md1) % md1;
  58.  
  59.     int hash2 = (pre2[r] - (pre2[l - 1] * pow2[r - l + 1])) % md2;
  60.     hash2 = (hash2 + md2) % md2;
  61.  
  62.     return {hash1, hash2};
  63. }
  64.  
  65. int32_t main()
  66. {
  67.     ios::sync_with_stdio(false);
  68.     cin.tie(NULL);
  69.     srand(time(NULL));
  70.     bs1 = Bs1[rand() % 9];
  71.     bs2 = Bs2[rand() % 9];
  72.     md1 = Md1[rand() % 9];
  73.     md2 = Md2[rand() % 9];
  74.     pow_cal();
  75.  
  76.     return 0;
  77. }
Success #stdin #stdout 0.02s 10436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yuUoGu
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!