Rolling Hash

Rolling hash represents substrings with hash values that can be updated or queried efficiently.

It is useful for fast substring comparison and pattern matching.

Core Idea

A string is treated like a polynomial over character values. Prefix hashes allow the hash of any substring to be computed by subtracting earlier contribution and adjusting powers.

This can make substring comparison very fast, but equal hashes do not absolutely guarantee equal strings unless collision handling is addressed.

Python Example

def build_hashes(text, base, mod):
    prefix = [0]
    power = [1]
 
    for char in text:
        prefix.append((prefix[-1] * base + ord(char)) % mod)
        power.append((power[-1] * base) % mod)
 
    return prefix, power

The prefix and power arrays are enough to compute many substring hashes.

Common Confusions

Rolling hash is not collision-free by default. Two different substrings can have the same hash.

Using Python’s built-in hash() is not the same thing. Algorithmic rolling hash needs stable arithmetic and substring formulas.

When To Use It

Use rolling hash for repeated substring comparison, duplicate substring detection, and pattern matching when probabilistic hashing is acceptable or collisions are checked.