Rolling hash and Rabin-Karp

Comparing two numbers takes one step; comparing two strings of length m can take m. A rolling hash turns every piece of the text into a number, and moves from one piece to the next in O(1). The Rabin–Karp method (1987) uses it to compare letters only where the numbers agree.

Compare numbers, not letters

HASH-1 built the polynomial hash of a string: treat the letter codes c₀, c₁, … as the digits of a number in base B,

h(s) = c₀·B^m−1 + c₁·B^m−2 + … + c_m−1,

and keep only the remainder after dividing by a large prime M, called the modulus. Here B^m−1 means m − 1 copies of B multiplied together. MATH-2 showed that you can take the remainder after every addition and multiplication and still get the right remainder at the end, so the numbers stay small.

If two strings are equal, their hashes are equal. The other way round is not guaranteed: two different strings can have the same hash, which is called a collision. So equal hashes mean “probably equal”, and different hashes mean “certainly different”.

Rolling the hash

Take the piece of T at place i, T[i..i+m−1], and the next piece, T[i+1..i+m]. They share m − 1 letters. In base 10 with the digits 31415926 and m = 3, going from 314 to 141 means: take away the first digit’s worth (300), multiply by 10, add the new digit (1). The same works in any base:

Here B^m−1 means m − 1 copies of B multiplied together. With B^m−1 mod M worked out once, each roll costs a few multiplications: O(1), whatever m is. The Rabin–Karp method rolls through the whole text and compares letters only where the hash equals the pattern’s hash. Step through the figure; it uses digits and M = 13 so that the numbers are easy to check.

def rabin_karp(t, p, B=131, M=(1 << 61) - 1):
    n, m = len(t), len(p)
    if m > n:
        return []
    top = pow(B, m - 1, M)            # B to the power m-1, mod M
    hp = ht = 0
    for k in range(m):
        hp = (hp * B + ord(p[k])) % M
        ht = (ht * B + ord(t[k])) % M
    found = []
    for i in range(n - m + 1):
        if ht == hp and t[i:i + m] == p:      # check the letters
            found.append(i)
        if i + m < n:                         # roll to place i + 1
            ht = ((ht - ord(t[i]) * top) * B + ord(t[i + m])) % M
    return found

(1 << 61) - 1 is 2⁶¹ − 1, a prime. Python’s % always gives a result from 0 to M − 1, even when the number before it is negative, so the subtraction needs no extra care.

Cost. The rolls cost O(n + m). Each letter check costs O(m), and it runs at every true occurrence and at every collision. With few collisions the total is O(n + m + m · k), where k is the number of occurrences. If the pattern occurs at almost every place, checking letters every time is O(n · m) again; then either trust the hash (and accept a tiny chance of error) or use KMP.

How often hashes collide

Take two different strings x and y of length m, and pick the base B at random from 0 to M − 1. The difference h(x) − h(y) is a polynomial in B of degree at most m − 1 that is not zero everywhere (the two strings differ in some letter). Modulo a prime, such a polynomial has at most m − 1 roots: values of B that make it 0 (the same fact as for ordinary polynomials, because division works modulo a prime, MATH-5). So:

Over all n places of a search, the chance of any collision is at most n · m / M. With n = m = 10⁶ and M ≈ 2.3 × 10¹⁸, that is less than one in a million. With M = 10⁹ + 7 it is useless: 10¹² / 10⁹ is more than 1.

A different danger comes from comparing many pieces with each other, as the practice problem does. With k different pieces, there are about k²/2 pairs, and each pair can collide. By the birthday problem (MATH-7), with a modulus near 10⁹ a collision becomes likely once there are about 50,000 pieces. With 2⁶¹ − 1, it takes a few billion.

Hashes of every piece

Store the hash of every start of the string, H[k] = h(s[0..k)), and the powers B^k mod M. Then the hash of any piece s[l..r) is

h(s[l..r)) = H[r] − H[l] · B^r−l (mod M),

because H[r] is H[l] moved up by r − l places plus the piece itself. Building the two lists costs O(n); each piece’s hash then costs O(1). This answers many questions quickly:

• Are two pieces equal? Compare their hashes.
• The longest common prefix of two pieces: binary search on the length (BSRC-4), comparing hashes: O(log n).
• The longest piece that occurs twice: if some piece of length L occurs twice, then so does a piece of every shorter length (its start). So binary search on L, and for each L put the hashes of all pieces of length L in a set: O(n log n). This is the practice problem.
• Is a piece a palindrome? Also hash the reversed string, and compare the hash of the piece with the hash of its mirror piece.

def prefix_hashes(s, B, M):
    H = [0] * (len(s) + 1)
    P = [1] * (len(s) + 1)
    for k, ch in enumerate(s):
        H[k + 1] = (H[k] * B + ord(ch)) % M
        P[k + 1] = P[k] * B % M
    return H, P

def piece(H, P, M, l, r):           # hash of s[l:r]
    return (H[r] - H[l] * P[r - l]) % M

Choosing the base and the modulus

• The modulus: a large prime. In Python, whole numbers never overflow, so 2⁶¹ − 1 works directly, and products of two such numbers are still fast. Some people use two moduli near 10⁹ at once (a double hash), which in other languages fits 64-bit arithmetic.
• The base: larger than every letter code, and chosen at random when the program starts, for example random.randrange(256, M - 1). A fixed base is fine for practice, but not for input that someone can choose against you.
• Many patterns of one length: put the patterns’ hashes in a set and roll through the text once. Each place costs one set lookup, for any number of patterns.
• Python’s own hash() on strings is salted at random each time Python starts (HASH-4), so it changes between runs, and it cannot be rolled.

Now try STRG-P4, The longest repeated piece.