fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define LEN 1000005
  5. #define mod 1000000007///best for mod kora
  6. int base =10;
  7.  
  8. int power[LEN];
  9.  
  10. void init()///O(N)
  11. {
  12.     power[0]=1;
  13.     for(int i=1;i<LEN;i++) power[i]=(power[i-1]*base)%mod;
  14. }
  15. void prefixHash(string s,vector<int> &ph)///O(N)
  16. {
  17.  
  18.     int sum=0;
  19.     for(int i=0;i<s.size();i++)
  20.     {
  21.         sum*=base;sum%=mod;
  22.         sum+=(s[i]-'0');sum%=mod;/// STRING THEKE INTEGER CONVERSION
  23.  
  24.         ph[i]=sum;
  25.     }
  26.     cout<<sum<<endl;
  27.     for(auto x:ph)cout<<x<<" ";
  28.     cout<<endl;
  29.  
  30. }
  31. int calcHash(int l,int r,string s,vector<int> &ph)///O(1)
  32. {
  33.     if(l==0) return ph[r];
  34.     int tmp=(ph[r]-(ph[l-1]*power[r-l+1])%mod);
  35.    ///return (((ph[r]-(ph[l-1]*power[r-l+1])%mod)%mod)+mod)%mod;////tiMe complexity O(1) THAKA LAGBE..AO AJONNO POWER ARRAY BANABO
  36.    if(tmp<0) return (tmp%mod)+mod;
  37.    else return tmp;
  38. }
  39. int32_t main()
  40. {
  41.     init();///O(n)
  42.     string s="101245";
  43.         int n=s.size();
  44.     vector<int>ph(n);
  45.  
  46.     int l=1,r=3;
  47.     //calcHash(l,r,s,ph);
  48.     prefixHash(s,ph);///SUM KORTESI AND STRING THEKE INT CONVERSION
  49.         cout<<endl;
  50.  
  51.     cout<<calcHash(l,r,s,ph);
  52. }
  53.  
Success #stdin #stdout 0.01s 11328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
101245
1 10 101 1012 10124 101245 

12
https://ideone.com/TH5lx4
language:
C++ (gcc 8.3)
created:
2 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!