Rolling Hash (Rabin-Karp)

Intuition

Comparing two substrings character by character costs their length. Hashing compresses each string into one integer, so equal strings always get equal numbers and different strings almost always get different ones. Compare numbers instead of strings and the cost drops to O(1).

The standard choice is a polynomial hash: read the string as a number in base B, modulo a prime M.

hash(s) = (s[0] * B^(k-1) + s[1] * B^(k-2) + ... + s[k-1]) mod M

Two properties make it "rolling":

• Prefix hashes. h[i + 1] = h[i] * B + s[i], so all prefix hashes take one pass.
• Any substring in O(1). Just like a prefix sum: hash(s[l:r]) = h[r] - h[l] * B^(r - l) (mod M). Sliding a fixed-length window one step costs O(1) too.

Different strings can still collide. For two fixed different strings of length k and a random base, the hash difference is a nonzero polynomial in B of degree below k, so a collision happens with probability at most k / M. With M = 2^61 - 1 that is negligible even over billions of comparisons, which is why that modulus is the safe default.

When to use it in interviews / OAs

• Substring equality asked many times: "are these two substrings equal", "is s[l:r] a palindrome" (compare with the reversed string's hash).
• Pattern matching when you want something shorter than KMP (Rabin-Karp).
• "Longest substring that appears twice", "longest common substring of two strings": binary search on the length plus a hash set per length.
• Counting distinct substrings of a given length, repeated DNA sequences, distinct "echo" substrings.
• Comparing whole objects cheaply: serialized subtrees, rows of a grid, paths.

Template

Prefix hashes

import random

MOD = (1 << 61) - 1  # Mersenne prime
BASE = random.randrange(10**6, MOD - 1)  # random base: no fixed input can be built to collide


class StringHash:
    def __init__(self, s: str):
        n = len(s)
        self.h = [0] * (n + 1)  # h[i] = hash of s[:i]
        self.p = [1] * (n + 1)  # p[i] = BASE**i % MOD
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * BASE + ord(ch) + 1) % MOD  # +1: no character maps to 0
            self.p[i + 1] = self.p[i] * BASE % MOD

    def get(self, l: int, r: int) -> int:
        # hash of s[l:r] in O(1)
        return (self.h[r] - self.h[l] * self.p[r - l]) % MOD

Rabin-Karp matching

def rabin_karp(text: str, pattern: str) -> list[int]:
    m = len(pattern)
    if m > len(text):
        return []
    ht, target = StringHash(text), StringHash(pattern).get(0, m)
    return [i for i in range(len(text) - m + 1) if ht.get(i, i + m) == target]

If a wrong answer is unacceptable, confirm each hit with text[i:i + m] == pattern; that adds O(m) per reported match.

Longest duplicate substring: binary search on the length

If some substring of length L occurs twice, so does one of every shorter length (take its prefix). That monotonicity allows binary search; each check hashes all windows of one length.

def longest_duplicate_substring(s: str) -> str:
    sh = StringHash(s)

    def find_dup(length: int) -> int:  # start of a repeated window, or -1
        seen = set()
        for i in range(len(s) - length + 1):
            x = sh.get(i, i + length)
            if x in seen:
                return i
            seen.add(x)
        return -1

    lo, hi = 1, len(s) - 1
    best, start = 0, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        i = find_dup(mid)
        if i != -1:
            best, start = mid, i
            lo = mid + 1
        else:
            hi = mid - 1
    return s[start:start + best]

Palindrome test for any substring

s[l:r] is a palindrome iff it equals its reverse, i.e. the matching block of reversed(s).

def make_palindrome_checker(s: str):
    fwd, rev, n = StringHash(s), StringHash(s[::-1]), len(s)

    def is_pal(l: int, r: int) -> bool:  # is s[l:r] a palindrome?
        return fwd.get(l, r) == rev.get(n - r, n - l)

    return is_pal

Complexity

Building prefix hashes is O(n) time and memory; each substring hash is O(1). Rabin-Karp is O(n + m) expected. The longest duplicate substring costs O(n log n) expected (log of the length range, O(n) set operations per step). Python's big integers make % MOD products safe; in C++ use __int128 or the Mersenne-specific reduction for the 61-bit modulus.

Common pitfalls

• A character mapped to 0. With 'a' -> 0, "a", "aa" and "aaa" all hash to 0. Map characters to values from 1 up.
• Small modulus plus many comparisons. With M = 10^9 + 7, putting 10^5 hashes into one set already expects a collision (birthday bound: about n^2 / (2M) pairs collide). Use 2^61 - 1 or two independent moduli.
• A fixed, well-known base and modulus can be attacked by crafted inputs in contests and some OAs; randomize the base at runtime. The 2^64 natural-overflow hash has known adversarial strings.
• Negative values in languages where % can return negatives: add M before taking the remainder.
• Different substring formulas for left-to-right vs right-to-left polynomials. Pick one convention and derive get for it.
• Hashing slices. set(s[i:i + L] for i in ...) or hash(s[i:j]) copies and rehashes L characters each time, which quietly throws away the O(1) advantage; use get(l, r).

Interview variations

• Repeated DNA sequences. Fixed window length 10: slide the window and keep a set of hashes (or of the substrings themselves, since they are short).
• Longest duplicate substring / longest common substring. Binary search on length; for two strings, collect window hashes of one and probe with the other.
• Distinct echo substrings. Count substrings of the form aa by comparing get(i, i + L) with get(i + L, i + 2L).
• Longest common prefix of two suffixes in O(log n): binary search on the length with hash comparisons. It also compares two substrings lexicographically (look at the first differing character).
• Matching with at most k mismatches. Jump over equal stretches with the LCP binary search, at most k + 1 times per window.
• Hashing structures. Serialize subtrees (find duplicate subtrees) or rows, then compare hashes.