string hashing

core idea

$$\begin{array}{rl}\mathrm{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}$$

substrings

For the substring $s[l..r)$, let $H[k]={\sum }_{i=0}^{k-1}s[i]\cdot p^i$. Then

$$\mathrm{hash}(s[l..r))=\left(H[r]-H[l]\right)\cdot p^{-l}(\mathrm{mod}m),$$

where $p^{-l}$ is the modular inverse of $p^l$ modulo $m$.

so you basically store prefix hashes and filter out the leading coefficient to make it 1.

improving non-collision rate

a hash is defined in terms of a tuple (p,m)

Ideally you would have m to be a large prime and keep it constant and then just use several differen p’s

so hash then becomes a vector of ints for the ordered tuple (p1,p2,p3) and the same m used across.

some applications

• a cyclic shift invariant hash? can be computed in linear time as the $min(hash(allcyclicshifts))$