fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int N = 1e6 + 9;
  6.  
  7. int power(int n, int k, const int mod)
  8. {
  9.     int ans = 1 % mod;
  10.     n %= mod;
  11.     if (n < 0)
  12.         n += mod;
  13.     while (k)
  14.     {
  15.         if (k & 1)
  16.             ans = ans * n % mod;
  17.         n = n * n % mod;
  18.         k >>= 1;
  19.     }
  20.     return ans;
  21. }
  22.  
  23. int rng(int maxm) {
  24. 	static std::mt19937 gen(
  25. 	    std::chrono::steady_clock::now().time_since_epoch().count());
  26. 	return std::uniform_int_distribution<int>(0, maxm-1)(gen);
  27. }
  28.  
  29. const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
  30. const int p1 = rng(MOD1), p2 = rng(MOD2);
  31. // See which primes to use :)
  32. int ip1, ip2;
  33. pair<int, int> pw[N], ipw[N];
  34. void prec()
  35. {
  36.     pw[0] = {1, 1};
  37.     for (int i = 1; i < N; i++)
  38.     {
  39.         pw[i].first = 1LL * pw[i - 1].first * p1 % MOD1;
  40.         pw[i].second = 1LL * pw[i - 1].second * p2 % MOD2;
  41.     }
  42.     ip1 = power(p1, MOD1 - 2, MOD1);
  43.     ip2 = power(p2, MOD2 - 2, MOD2);
  44.     ipw[0] = {1, 1};
  45.     for (int i = 1; i < N; i++)
  46.     {
  47.         ipw[i].first = 1LL * ipw[i - 1].first * ip1 % MOD1;
  48.         ipw[i].second = 1LL * ipw[i - 1].second * ip2 % MOD2;
  49.     }
  50. }
  51. struct Hashing
  52. {
  53.     int n;
  54.     string s;                  // 0 - indexed
  55.     vector<pair<int, int>> hs; // 1 - indexed
  56.     Hashing() {}
  57.     Hashing(string _s)
  58.     {
  59.         n = _s.size();
  60.         s = _s;
  61.         hs.emplace_back(0, 0);
  62.         for (int i = 0; i < n; i++)
  63.         {
  64.             pair<int, int> p;
  65.             p.first = (hs[i].first + 1LL * pw[i].first * s[i] % MOD1) % MOD1;
  66.             p.second = (hs[i].second + 1LL * pw[i].second * s[i] % MOD2) % MOD2;
  67.             hs.push_back(p);
  68.         }
  69.     }
  70.     pair<int, int> get_hash(int l, int r)
  71.     { // 1 - indexed : index from 1 to n : get hash of a substring
  72.         pair<int, int> ans;
  73.         ans.first = (hs[r].first - hs[l - 1].first + MOD1) * 1LL * ipw[l - 1].first % MOD1;
  74.         ans.second = (hs[r].second - hs[l - 1].second + MOD2) * 1LL * ipw[l - 1].second % MOD2;
  75.         return ans;
  76.     }
  77.     pair<int, int> get_hash()
  78.     {
  79.         return get_hash(1, n);
  80.     }
  81. };
  82. signed main()
  83. {
  84.     ios_base::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     prec();
  87.     // Change the max length N at top
  88.  
  89.     // Do Hashing hash(sting)
  90.     // hash.get_hash(l,r) : 1 based indexing [1,n]
  91. }
Success #stdin #stdout 0.02s 34920KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/eTTm1u
language:
C++ (gcc 8.3)
created:
6 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!