Precompute the inverse of every p^i

I m learning Hashing from HERE , Now in this the topic “hash value of a substring”

             hash(s[i..j]) = ( (hashvalue upto j - hasvalue upto i-1 ) / p^i ) mod m
             hash(s[i..j]) = ( (hashvalue upto j - hasvalue upto i-1 ) * inversemod(p^i ) ) mod m

I m calcultaing prefix hashvalue (not suffix as many git repo use suffix (i m confusing in suffix so) ) Now I can easily calculate inversemod(p^i) by first calculating x = p^i mod m and then x^(m-2) mod m … fo for each power i it takes n(logn*logn) time , so how can precompute inverse of every p^i lesser than this time ?

@nishant403 @akashbhalotia @galencolin

u means modinv ( p ) = modinv( p ^ 2) = modinv(p^3) ? HOW ?

I think he said multiply out the rest, means modinv(p^2)= (modinv(p)*modinv(p))%mod and so on. Not sure though.

No, p^{-n}=(p^{-1})^n.

So \text{inversemod}(p^i) = p^{-1} \times \text{inversemod}(p^{i-1}), giving you a very efficient way to compute \text{inversemod}(p^i) for all i.

3 Likes

Check out this code, for hashing I have calculated mod multiplicative inverse for each p^i in the precomputation() function: https://www.codechef.com/viewsolution/33366890

1 Like
p_inv[1] = modinv(p)
x = p_inv[i]
for i =2 to n:
      p_inv[i] = (p_inv[i-1] * x)%m

Right ?

Buddy help me in this too

struct Hashs 
{
vector<int> hashs;
vector<int> pows;
int P;
int MOD;

Hashs() {}

Hashs(string &s, int P, int MOD) : P(P), MOD(MOD) 
{
	int n = s.size();
	pows.resize(n+1, 0);
	hashs.resize(n+1, 0);
	pows[0] = 1;
	for(int i=n-1;i>=0;i--) 
	{
		hashs[i]=(1LL * hashs[i+1] * P + s[i] - 'a' + 1) % MOD;
		pows[n-i]=(1LL * pows[n-i-1] * P) % MOD;
	}
	pows[n] = (1LL * pows[n-1] * P)%MOD;
}
int get_hash(int l, int r) 
{
	int ans=hashs[l] + MOD - (1LL*hashs[r+1]*pows[r-l+1])%MOD;
	ans%=MOD;
	return ans;
}
};

This code is from AshishGupta’s Repo … He calculates suffix hash values (now i understand) but in get_hash(l,r) function what did he do ?

In the above code. He is multiplying with power which is pre calculated. The reason here is, consider you have p^6+p^7+p^8 and p^2+p^3+p^4, Here we are using rolling hash, so we need to subtract r and l-1 right?. As p is raised to some power we cant directly subtract instead we raise both of them to equal powers, Now if we multiply p^2+p^3+p^4 with p^4 It becomes p^6+p^7+p^8, We have equal powers and can be subtracted and As we are calculating mod, hash[r] might be less than hash[l-1] so subtract with mod.Same with sufix also. prefix implementation

1 Like