PyInfo
String Algorithms contents

String Hashing and Rabin-Karp

Compare any two substrings in O(1) after O(n) preprocessing with polynomial hashes, and use rolling hashes to search for patterns.

Intermediate8 min readhashingrabin-karpsubstringsmodular arithmetic

Read first: Modular Multiplicative Inverse

Hashing maps a string to a number so that equal strings always get equal numbers and different strings almost always get different numbers. Comparing two numbers is O(1)O(1) no matter how long the strings are. Combined with prefix sums, it gives an O(1)O(1) test for "are these two substrings equal?".

Polynomial hash

Choose a base pp and a modulus mm and define

hash(s)=(s0 p n−1+s1 p n−2+⋯+sn−1) mod m\text{hash}(s) = \left(s_0\, p^{\,n-1} + s_1\, p^{\,n-2} + \dots + s_{n-1}\right) \bmod m

where sis_i is the character code. This is exactly how a number is read digit by digit (Horner's rule), with the base pp playing the role of 10.

Typical choices: mm large and prime; pp larger than the alphabet size and, importantly, random.

python
import random

MOD = (1 << 61) - 1                       # a Mersenne prime: 2305843009213693951
BASE = random.randrange(10 ** 5, MOD - 1)

def poly_hash(s):
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch)) % MOD
    return h

assert poly_hash("hello") == poly_hash("hello")
assert poly_hash("hello") != poly_hash("hellp")

Why a random base and a big modulus?

If two different strings collide, the algorithm gives a wrong answer. For a random base and a prime modulus mm the probability that a given pair collides is about n/mn/m. With m≈109m \approx 10^9 and 10610^6 comparisons, collisions are likely (birthday paradox); with m=261−1m = 2^{61} - 1 they are negligible. In Python, big integers make the 61-bit modulus painless, which is one of the places where Python is more convenient than C++.

Substring hashes in O(1)O(1)

Precompute prefix hashes h[i]=hash(s[0:i])h[i] = \text{hash}(s[0:i]) (so h[i+1]=h[i]⋅p+sih[i+1] = h[i]\cdot p + s_i) and the powers of the base. Appending characters to a prefix multiplies its old value by pp for each one, so removing the prefix s[0:l]s[0:l] from h[r]h[r] means subtracting h[l]⋅p r−lh[l]\cdot p^{\,r-l}:

hash(s[l:r])≡h[r]−h[l] p r−l(modm)\text{hash}(s[l:r]) \equiv h[r] - h[l]\, p^{\,r-l} \pmod m

The result does not depend on where the substring sits, so hashes of substrings taken from different places (or even different strings, with the same pp and mm) can be compared directly. No modular inverse is needed.

python
class StringHash:
    def __init__(self, s, base=None, mod=MOD):
        self.mod = mod
        self.base = base if base is not None else random.randrange(10 ** 5, mod - 1)
        n = len(s)
        self.h = [0] * (n + 1)
        self.pw = [1] * (n + 1)
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * self.base + ord(ch)) % mod
            self.pw[i + 1] = self.pw[i] * self.base % mod

    def get(self, l, r):
        """Hash of s[l:r]; equals poly_hash(s[l:r]) when the base and modulus are the same."""
        return (self.h[r] - self.h[l] * self.pw[r - l]) % self.mod

s = "abracadabra"
H = StringHash(s)
assert H.get(0, 4) == H.get(7, 11)              # "abra" == "abra"
assert H.get(0, 4) != H.get(1, 5)               # "abra" != "brac"
assert H.get(2, 2) == H.get(5, 5) == 0          # empty substrings

# a randomized comparison with direct string equality
random.seed(1)
for _ in range(300):
    t = "".join(random.choice("ab") for _ in range(random.randint(1, 30)))
    Ht = StringHash(t)
    for _ in range(20):
        length = random.randint(0, len(t))
        i = random.randint(0, len(t) - length)
        j = random.randint(0, len(t) - length)
        assert (Ht.get(i, i + length) == Ht.get(j, j + length)) == (t[i : i + length] == t[j : j + length])

get agrees with hash(s) computed on the substring alone:

python
H2 = StringHash("xxabracadabrayy", base=BASE)
assert H2.get(2, 13) == poly_hash("abracadabra")

Applications

Slide a window of length m=∣t∣m = |t| over ss; compare the window's hash to the pattern's hash. If equal (almost surely a match), report the position. It's O(n+m)O(n + m) expected.

python
def rabin_karp(s, t):
    """All start positions of t in s."""
    n, m = len(s), len(t)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []
    Ht = StringHash(t)
    Hs = StringHash(s, base=Ht.base)                       # both strings must use the same base
    target = Ht.get(0, m)
    return [i for i in range(n - m + 1) if Hs.get(i, i + m) == target]

def find_all(s, t):
    out, i = [], s.find(t)
    while i != -1:
        out.append(i)
        i = s.find(t, i + 1)
    return out

assert rabin_karp("abracadabra", "abra") == [0, 7]
assert rabin_karp("aaaaa", "aa") == [0, 1, 2, 3]
assert rabin_karp("abc", "abcd") == []
for _ in range(200):
    text = "".join(random.choice("ab") for _ in range(random.randint(0, 40)))
    pat = "".join(random.choice("ab") for _ in range(random.randint(1, 4)))
    assert rabin_karp(text, pat) == find_all(text, pat)

Number of distinct substrings of a given length

Put the hashes of all length-kk substrings into a set; its size is the answer. That is O(n)O(n) for one kk.

python
def distinct_substrings_of_length(s, k):
    H = StringHash(s)
    return len({H.get(i, i + k) for i in range(len(s) - k + 1)})

assert distinct_substrings_of_length("abababc", 2) == 3        # ab, ba, bc
assert distinct_substrings_of_length("aaaa", 2) == 1

Summing over every kk counts all distinct substrings in O(n2)O(n^2); a suffix array does it in O(nlog⁡n)O(n \log n).

If a substring of length kk occurs twice, so does one of length k−1k - 1 (shorten it). That monotonicity lets you binary search kk, checking each with a set of hashes:

python
def longest_repeated_substring(s):
    H = StringHash(s)

    def has_repeat(k):
        seen = {}
        for i in range(len(s) - k + 1):
            h = H.get(i, i + k)
            if h in seen:
                return seen[h]
            seen[h] = i
        return None

    lo, hi, best = 1, len(s) - 1, ""
    while lo <= hi:
        mid = (lo + hi) // 2
        pos = has_repeat(mid)
        if pos is not None:
            best = s[pos : pos + mid]
            lo = mid + 1
        else:
            hi = mid - 1
    return best

assert longest_repeated_substring("banana") == "ana"
assert longest_repeated_substring("abcd") == ""

Other uses

  • Checking whether two strings are cyclic shifts of each other.
  • Finding palindromic substrings: compare a hash of the substring with the hash of its reverse.
  • Comparing trees or other structures by hashing a canonical string form.

Choosing parameters

Setting Choice
modulus 261−12^{61} - 1 (Python: free) or two independent moduli around 10910^9
base random in [ alphabet,m)[\,\text{alphabet}, m), chosen at run time
character value ord(ch) (never 00, so "a" and "aa" differ)
direction any, consistently

Practice problems

This article is a Python adaptation of “String Hashing” from cp-algorithms.com, licensed under CC BY-SA 4.0. The text was condensed and rewritten and the C++ code was reimplemented in Python; this adaptation is shared under the same license.