Rolling Hash

Update a substring's hash in $O(1)$ when the window slides.

Intermediate

$h = (h - s[i]\cdot B^{m-1})\cdot B + s[i+m] \pmod p$ . Use large primes or double hashing to reduce collisions.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)