Rolling Hash / Rabin-Karp

The problem with naive substring search

Suppose you want to check whether a 10-character pattern exists somewhere inside a 1 000 000-character text. The brute-force approach compares the pattern against every possible 10-character window. There are ~1 000 000 windows and each comparison takes up to 10 steps — O(n × k) total.

For n = 1 000 000 and k = 10 that is 10 million character comparisons. Manageable here, but what if k is 10 000? Or the pattern itself is 100 000 characters? The cost explodes.

The pain point is recomputing the window's identity from scratch every time the window slides. Surely we can do better?

The conveyor-belt scanner story

The turning point

The polynomial rolling hash

A polynomial hash assigns each character a weight based on its position:

$$h = \sum_{i=0}^{k-1} \text{char}[i] \times \text{base}^{k-1-i} \pmod{MOD}$$

For a 3-character window "abc" with base 31:

$$h = a \times 31^2 + b \times 31^1 + c \times 31^0$$

When the window slides right by one (losing 'a', gaining 'd'):

$$h_{\text{new}} = (h - a \times \text{base}^{k-1}) \times \text{base} + d \pmod{MOD}$$

This is the rolling step — O(1).

The one idea to remember

Frame-by-frame: Rolling "abc" → "bcd"

Text: a b c d e, window size k = 3, base = 31, MOD = 10^9 + 7.

Initial window [a, b, c]:
h = ord('a') * 31^2 + ord('b') * 31^1 + ord('c') * 31^0
  = 97 * 961   + 98 * 31   + 99 * 1
  = 93217      + 3038       + 99
  = 96354

Slide right — lose 'a', gain 'd':
Step 1: subtract leftmost contribution:
        h = h - ord('a') * 31^2
          = 96354 - 93217
          = 3137

Step 2: multiply by base (shift remaining chars left one position):
        h = h * 31
          = 3137 * 31
          = 97247

Step 3: add new rightmost character:
        h = h + ord('d')
          = 97247 + 100
          = 97347

New window [b, c, d]:
Verify: 98 * 961 + 99 * 31 + 100 = 94178 + 3069 + 100 = 97347  ✅

Three O(1) arithmetic steps, no re-scanning of the window.

Code, line by line

def rabin_karp(text: str, pattern: str) -> list[int]:
    n, k = len(text), len(pattern)
    if k > n:
        return []

    BASE = 31
    MOD  = 10**9 + 7

    # Precompute base^(k-1) mod MOD — used to remove the leftmost character
    high_power = pow(BASE, k - 1, MOD)

    def char_val(c):
        return ord(c) - ord('a') + 1   # 'a'=1, 'b'=2, ..., 'z'=26

    # Hash the pattern
    pattern_hash = 0
    for c in pattern:
        pattern_hash = (pattern_hash * BASE + char_val(c)) % MOD

    # Hash the first window
    window_hash = 0
    for c in text[:k]:
        window_hash = (window_hash * BASE + char_val(c)) % MOD

    results = []
    if window_hash == pattern_hash:
        if text[:k] == pattern:           # verify to rule out hash collision
            results.append(0)

    # Slide the window
    for i in range(k, n):
        # Remove leftmost character (index i - k)
        window_hash = (window_hash - char_val(text[i - k]) * high_power) % MOD
        # Shift and add rightmost character
        window_hash = (window_hash * BASE + char_val(text[i])) % MOD
        # Ensure non-negative (Python % is always ≥ 0, but explicit guard is good habit)
        window_hash %= MOD

        start = i - k + 1
        if window_hash == pattern_hash:
            if text[start:start + k] == pattern:   # O(k) only on hash match
                results.append(start)

    return results

Line-by-line narration:

• high_power = pow(BASE, k-1, MOD) — this is the weight of the leftmost character. Pre-compute once.
• pattern_hash — computed once before the loop. O(k).
• First window hash — computed by treating each character as the next coefficient. O(k).
• Inside the loop: three arithmetic operations per step. O(1) each.
• text[start:start+k] == pattern — the "verify" step, runs only on a hash match. Prevents reporting false positives caused by hash collisions.

Time complexity: O(n + k) amortised. The verify step costs O(k) but only triggers on actual or colliding matches; with good constants it stays rare.

A cleaner form for some problems — the additive form

Some interview problems (like "Repeated DNA Sequences") don't need position-sensitive hashing because they search for exact string matches. They can use Python's built-in hash() on substrings, or a simpler numeric encoding like the four-base DNA encoding:

def findRepeatedDnaSequences(s: str) -> list[str]:
    seen = set()
    repeated = set()
    mapping = {'A': 0, 'C': 1, 'G': 2, 'T': 3}

    # Build hash using 2-bit encoding: each char uses 2 bits, window uses 20 bits
    k = 10
    mask = (1 << (2 * k)) - 1    # 20-bit mask

    curr = 0
    for i, c in enumerate(s):
        curr = ((curr << 2) | mapping[c]) & mask   # shift in new char, mask out old
        if i >= k - 1:                              # window is full
            if curr in seen:
                repeated.add(s[i - k + 1: i + 1])
            seen.add(curr)

    return list(repeated)

The << 2 shift is the rolling step: it moves all existing bits left by 2, making room for the new character's 2 bits, and & mask drops the leftmost character automatically (the mask is exactly k characters wide).

Frame-by-frame for s = "AAAAACCCCC AAAAACCCCC" (k=10):

After reading positions 0–9:  curr = 0b 00 00 00 00 00 01 01 01 01 01  (AAAAACCCCC)
                                        A  A  A  A  A  C  C  C  C  C
                                        
After reading position 10 (A):
  curr << 2:  shifts everything left, drops the leftmost A bits (masked out)
  new bit: 00 (A)
  curr = 0b 00 00 00 00 01 01 01 01 01 00  (AAAACCCCC A)

...

After positions 10–19: same hash as positions 0–9 → duplicate found → "AAAAACCCCC"

Double hashing — defeating collision attacks

A single hash can produce false positives. In interviews, it's usually fine to add the text[start:start+k] == pattern verify step. In competitive programming or production, use double hashing: maintain two independent (BASE, MOD) pairs. A false positive in both is astronomically unlikely.

# Two independent hashes
h1, h2 = 0, 0
BASE1, MOD1 = 31, 10**9 + 7
BASE2, MOD2 = 37, 10**9 + 9

# Update: apply rolling step to both
h1 = (h1 * BASE1 + char_val(c)) % MOD1
h2 = (h2 * BASE2 + char_val(c)) % MOD2

# Compare both
if (h1, h2) == (pattern_h1, pattern_h2):
    # Match (essentially guaranteed to be real)

Where to spot this pattern

Trigger words:

• "matching in a string" where k is large
• "find all occurrences of a pattern in text"
• "longest duplicate substring" (binary search on length + rolling hash)
• "repeated DNA sequences" / "repeated substrings"
• "distinct substrings" of a given length
• "anagram occurrences" (use frequency-based hash instead)

5 disguises:

1. Repeated DNA Sequences (LC #187): k=10, binary rolling hash with 2-bit encoding per base.
2. Longest Duplicate Substring (LC #1044): binary search on length; rolling hash check in O(n). Binary search × O(n) = O(n log n).
3. Rabin-Karp exact pattern match: multiple pattern occurrences in one pass.
4. Longest Substring Without Repeating Character: this one uses a sliding window with a set, not rolling hash — don't confuse them.
5. Check if two strings are anagrams of all substrings: use a frequency-difference hash (XOR of char frequencies) to compare windows.

Common traps

Complexity

For "Longest Duplicate Substring": O(n log n) — binary search over length O(log n) × rolling hash scan O(n).

Say it like a pro (interview one-liner)

"I'll use a rolling polynomial hash to slide a k-wide fingerprint across the string in O(1) per step. Each slide subtracts the leaving character's weighted contribution and adds the entering character's. On a hash match I do an O(k) string verify to rule out collisions. Total: O(n + k) time, O(1) extra space."

high_power = BASE^(k-1) % MOD

# Build first window hash — O(k)
h = Σ char_val(s[i]) * BASE^(k-1-i)  % MOD

# Slide — O(1) per step
h = (h - char_val(leaving) * high_power) % MOD
h = (h * BASE + char_val(entering))    % MOD
h %= MOD  # ensure non-negative

# On match, verify with direct comparison

Check yourself

Practice problems

Next up: HashSet for Duplicate / Existence Check — the simplest hash structure, used when you only need "have I seen this before?"