Sarwar_450's blog

By Sarwar_450, history, 3 years ago, In English

I have been trying to make my hash template faster for a few days now but I can't seem to find any more optimizations. I noticed that my single hash runs slower than some people's double hash. Can someone tell me where I'm going wrong?




typedef long long ll; int powhash1[ 1000000+ 10]={}; int powhash2[ 1000000+ 10]={}; int prefhash1[1000000 + 10]; int prefhash2[1000000 + 10]; int add(ll x,ll y,ll mod) { return (x+y>=mod)?(x+y-mod):(x+y); } int subtract(ll x,ll y,ll mod) { return (x-y<0)?(x-y+mod):(x-y); } int multp(ll x,ll y,ll mod) { return (x*y)%mod; } ll BASE1 = 125; ll MOD1 = 1e9 + 9; ll BASE2 = 250; ll MOD2 = 1e9 + 7; void prefhashcalc(string s,ll base,ll mod,int*prefhash) { ll sum = 0; int ns = s.size(); for(int i=0;i<ns;i++) { sum = add((sum*base)%mod,s[i]-'A'+1,mod); prefhash[i]=sum; } } ll strhash(string s,ll base,ll mod) { ll sum = 0; int ns = s.size(); for(int i=0;i<ns;i++) { sum = add((sum*base)%mod,s[i]-'A'+1,mod); } return sum; } void powhashfill(ll base,ll mod,int*powhash) { for(int i=0;i<1000000 + 10;i++) { if(i==0) { powhash[0]=1; continue; } powhash[i] = multp(powhash[i-1],base,mod); } } ll substrhash(int l,int r,ll mod,int*prefhash,int*powhash) { ll x = subtract( prefhash[r], multp(prefhash[l-1],powhash[r-l+1],mod), mod ); return x; }

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it