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.

Function Contracts

build_hashes(text, base, mod) expects a string, a base, and a modulus. It returns prefix hashes and base powers.

substring_hash(prefix, power, left, right, mod) expects a half-open range [left, right) and returns the hash for that substring under the same base and modulus.

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.

Substring Hash Idea

After prefix hashes are built, a substring hash can be computed in constant time:

def substring_hash(prefix, power, left, right, mod):
    return (prefix[right] - prefix[left] * power[right - left]) % mod

This treats the substring as the range [left, right).

Why It Helps

Naive substring comparison may compare many characters. Rolling hash turns a substring into a numeric signature. If two signatures differ, the substrings are definitely different. If they match, the substrings are probably equal unless a collision occurred.

Collision Handling

A collision happens when different substrings produce the same hash. Common ways to reduce risk are using a large modulus, using two independent hashes, or verifying the actual strings when needed.

Complexity

Building prefix hashes is O(n). Each substring hash query is O(1). Extra space is O(n).

Failure Example

Two different substrings can have the same hash. If the algorithm treats equal hashes as absolute proof of equal strings, it can return a false match.

Use verification, double hashing, or a collision-tolerant problem setting when correctness must be exact.

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.

Another common mistake is mixing inclusive and exclusive substring boundaries. Decide whether the range is [left, right] or [left, right) and keep the formula consistent.

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.

Do not use it when exact deterministic comparison is required and collision handling is not acceptable.

The Main Point

Rolling hash makes substring comparison fast by turning substrings into arithmetic signatures, but collisions must be handled or accepted.