Help in Rolling Hashing for Strings

help
1

Here is a piece of code taken from the github repository of Ashish Gupta

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

I have two doubts here.

  1. Can’t the loop can be run from 0 to n to generate the hash as given on the CP Algorithms Page. Will it be wrong.
  2. How is getHash(int l, int r) implemented. Meaning how it is giving the hash value for a given range.

@everule1 @akashbhalotia @vijju123 @waqar_ahmad224

2

Please Format your code.

This is a polynomial hash. It doesn’t matter at all as long as the hash value for a zero indexed string is \sum S_iP^i.

hashs[i] contains the suffix hash from i to n.
Therefore hashs[i] = \sum_{j=i}^{n-1} S_jP^{j-i}

The hash of a substring is \sum_{i=l}^r S_iP^{i-l}.
Which is equal to (\sum_{i=l}^{n-1} S_iP^{i-l}) - (\sum_{i=r+1}^{n-1} S_iP^{i-l}).

Now we can convert the second summation into the suffix hash of r+1.

(\sum_{i=l}^{n-1} S_iP^{i-l}) - (\sum_{i=r+1}^{n-1} S_iP^{i-r-1})P^{r+1-l}.

Which is hashs[l] - hashs[r+1]\times P^{r+1-l}

4 Likes
3

Thanks a lot @everule1.