String Hashing

Code

We need a hash function to convert a string into an integer, called the hash of that string. The following condition has to hold: For two strings $S$ and $T$,

$$S=T⟹\text{hash}(S)=\text{hash}(T)$$

but reverse is not guaranteed. We only hope that

$$P(S\ne T⟹\text{hash}(S)\ne \text{hash}(T))\text{is very high}$$

Polynomial Rolling Hash Function

$$\begin{array}{rl}\text{hash}(s)& =s[0]+s[1]\cdot p+s[2]\cdot p^2+\cdots +s[n-1]\cdot p^{n-1}\mathrm{mod}m\\ & =\sum _{i=0}^{n-1}s[i]\cdot p^i\mathrm{mod}m,\end{array}$$

where $n=\text{length}(s)$ and $p$ and $m$ are some chosen, positive numbers.

caution

For example while calculating the hash of string $s$ made of only lowercase letters, we convert each character of $s$ to an integer. A possible conversion is $a\to 1,b\to 2,\cdots ,z\to 26$. Converting $a\to 0$ is not a good idea, because then the hashes of the strings $a,aa,aaa,\cdots$ all evaluate to 0.

// Precomputing the powers of p might give a performance boost.

Technique: Fast Polynomial Rolling Hash of Substrings