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;
}