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