fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define LEN 1000000
  4. int power[LEN];
  5. int base = 10;
  6.  
  7. void init()
  8. {
  9.     power[0] = 1;
  10.     for (int i = 1; i < LEN; i++)
  11.     {
  12.         power[i] = power[i - 1] * base;
  13.     }
  14. }
  15.  
  16. void prefixHash(string str, vector<int> &ph)
  17. {
  18.     int n = str.size();
  19.     int sum = 0;
  20.     for (int i = 0; i < n; i++)
  21.     {
  22.         sum *= base;
  23.         sum += (str[i] - '0');
  24.         ph[i] = sum;
  25.     }
  26.     cout << sum << "\n";
  27.     for (int num : ph)
  28.     {
  29.         cout << num << " ";
  30.     }
  31. }
  32.  
  33. int calcHash(int l, int r, vector<int> &ph)
  34. {
  35.     if (l == 0)
  36.         return ph[r];
  37.     return ph[r] - ph[l - 1] * power[r - l + 1];
  38. }
  39.  
  40. int main()
  41. {
  42.     string str = "101245";
  43.  
  44.     int n = str.size();
  45.  
  46.     vector<int> ph(n);
  47.  
  48.     int l = 2  , r = 3;
  49.  
  50.     init();
  51.     prefixHash(str, ph);
  52.     cout << "\n";
  53.     cout << "Calculated Hash: " << calcHash(l, r, ph) << endl;
  54.  
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 7508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
101245
1 10 101 1012 10124 101245 
Calculated Hash: 12
https://ideone.com/EUPssE
language:
C++ (gcc 8.3)
created:
3 hours 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!