fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define LEN 1000005
  4. int base =10;
  5.  
  6. int power[LEN];
  7.  
  8. void init()
  9. {
  10.     power[0]=1;
  11.     for(int i=1;i<LEN;i++) power[i]=power[i-1]*base;
  12. }
  13. void prefixHash(string s,vector<int> &ph)
  14. {
  15.  
  16.     int sum=0;
  17.     for(int i=0;i<s.size();i++)
  18.     {
  19.         sum*=base;
  20.         sum+=(s[i]-'0');
  21.         ph[i]=sum;
  22.     }
  23.     cout<<sum<<endl;
  24.     for(auto x:ph)cout<<x<<" ";
  25.     cout<<endl;
  26.  
  27. }
  28. int calcHash(int l,int r,string s,vector<int> &ph)
  29. {
  30.     if(l==0) return ph[r];
  31.    return ph[r]-ph[l-1]*power[r-l+1];
  32. }
  33. int main()
  34. {
  35.     init();
  36.     string s="101245";
  37.         int n=s.size();
  38.     vector<int>ph(n);
  39.  
  40.     int l=1,r=3;
  41.     //calcHash(l,r,s,ph);
  42.     prefixHash(s,ph);
  43.         cout<<endl;
  44.  
  45.     cout<<calcHash(l,r,s,ph);
  46. }
  47.  
Success #stdin #stdout 0.01s 7504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
101245
1 10 101 1012 10124 101245 

12
https://ideone.com/xZ2WT6
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!