Rolling hash (Rabin-Karp)

advancedCommon atGoogleMetatrading firmsAmazonRead firstHash mapsSliding windowMath and number handlingPractise in the Sandbox →

A polynomial hash treats a string as a number in base B, reduced mod M: h(s) = s₀·B^(k−1) + s₁·B^(k−2) + … + s_(k−1). Sliding a window one place is O(1): subtract the leaving character’s term, multiply by B, add the new character. Equal strings always hash equal; unequal strings collide with probability about 1/M, so either verify hits or use a huge modulus (or two). Rabin-Karp search runs in O(n + m) expected.

The idea in plain words

Comparing two length-k strings costs k character comparisons. If you need to compare many windows (every length-k window of a long text against a pattern, or against each other), that’s O(n·k).

A hash turns each window into a single number, so comparing two windows costs O(1). The trick is computing those numbers cheaply. Think of the window as digits of a number. In base 10, sliding 1234 to 2345 means: remove the leading 1·1000, shift left (×10), add 5. No need to look at 2, 3, 4 again. A rolling hash does exactly that with base B (bigger than the alphabet) and keeps the numbers small by working modulo M.

The catch: reducing mod M squeezes infinitely many strings into M buckets, so different strings can land on the same hash. That’s a collision (in a search, a spurious hit). Two defences:

• Verify: on a hash match, compare the actual characters. Correct always; slow only if hits are frequent.
• Make collisions improbable: a large prime M (around 10⁹ or 2⁶¹ − 1), a random base, or two independent hashes compared as a pair.

See it

The default uses a deliberately tiny M = 13, so a spurious hit shows up. Watch the window hash row fill in O(1) per step, then raise M or switch on double hashing and watch the collision disappear. Try B = 26, M = 13 to see what a bad base/mod pair does.

Rolling a window hash

step through

text (a-z, ≤ 18)pattern (≤ 6)base Bmod M

a

b

c

a

b

d

c

a

b

d

a

c

b

d

a

b

0123456789101112131415

hash of the window starting here

hash("cab") = ((3)·31 + 1)·31 + 2 mod 13 = 4

pattern hash4

current windowits hashverified matchspurious hit (collision)

Hash the pattern once with Horner's rule: treat "cab" as a number in base 31, reduced mod 13. Letters are a=1 … z=26.

↺◀▶ Play▶1 / 16

When to reach for it

The problem says…	Why a rolling hash fits
find a pattern in a text, and simplicity matters more than a worst-case guarantee	Rabin-Karp: hash the pattern, roll over the text, verify hits.
many substring-equality questions on one string	Prefix hashes give any substring’s hash in O(1).
compare every window of length k against a pattern or a small set of patterns	Rolling removes the factor k from each window.
2-D pattern search in a grid	Roll rows, then roll columns of row hashes.
need a guaranteed O(n + m) single-pattern search	Prefer KMP or the Z-function.

How it works

1. Map characters to numbers, never 0 (use code points, or a = 1 … z = 26), so "a" and "aa" differ.
2. Hash the first window with Horner’s rule: h = h·B + c (mod M) for each character. O(k).
3. Roll: precompute top = B^(k−1) mod M. To drop out and add in: h = ((h − out·top)·B + in) mod M. Keep it non-negative.
4. Confirm a hash match by comparing characters (or accept the tiny error probability of a 2⁶¹-size or double hash, and say so).

The roll step, checked against recomputing every window from scratch:

Python

roll.py

B, M = 131, 1_000_000_007          # base > alphabet size; large prime modulus


def poly_hash(s: str) -> int:
    """h(s) = s[0]*B^(k-1) + s[1]*B^(k-2) + ... + s[k-1]  (mod M), via Horner's rule."""
    h = 0
    for ch in s:
        h = (h * B + ord(ch)) % M    # 1. shift left one "digit", add the new one
    return h


def roll(h: int, out_ch: str, in_ch: str, top: int) -> int:
    """Slide a window one place: drop out_ch on the left, append in_ch on the right.
    top = B^(k-1) mod M, precomputed once for window length k."""
    h = (h - ord(out_ch) * top) % M  # 2. remove the leading term (Python % is never negative)
    return (h * B + ord(in_ch)) % M  # 3. shift and add, exactly as in Horner


if __name__ == "__main__":
    text, k = "the quick brown fox", 5
    top = pow(B, k - 1, M)           # 3-arg pow: modular exponentiation
    h = poly_hash(text[:k])
    for i in range(1, len(text) - k + 1):
        h = roll(h, text[i - 1], text[i + k - 1], top)
        assert h == poly_hash(text[i:i + k])   # rolling == recomputing from scratch
    print("ok")

TypeScript

roll.ts

import assert from "node:assert/strict";

// Use BigInt: (M-1) * B can exceed 2^53, where JS numbers silently lose precision.
const B = 131n, M = 1_000_000_007n; // base > alphabet size; large prime modulus
const code = (ch: string) => BigInt(ch.charCodeAt(0));

/** h(s) = s[0]*B^(k-1) + ... + s[k-1]  (mod M), via Horner's rule. */
export function polyHash(s: string): bigint {
  let h = 0n;
  for (const ch of s) h = (h * B + code(ch)) % M; // 1. shift left one "digit", add the new one
  return h;
}

/** Slide one place: drop outCh on the left, append inCh. top = B^(k-1) mod M. */
export function roll(h: bigint, outCh: string, inCh: string, top: bigint): bigint {
  h = (h - code(outCh) * top) % M; // 2. remove the leading term ...
  if (h < 0n) h += M; //    ... JS % keeps the sign, so fix negatives
  return (h * B + code(inCh)) % M; // 3. shift and add, exactly as in Horner
}

function powMod(b: bigint, e: number, m: bigint): bigint {
  let r = 1n;
  for (let i = 0; i < e; i++) r = (r * b) % m;
  return r;
}

const text = "the quick brown fox", k = 5;
const top = powMod(B, k - 1, M);
let h = polyHash(text.slice(0, k));
for (let i = 1; i + k <= text.length; i++) {
  h = roll(h, text[i - 1], text[i + k - 1], top);
  assert.equal(h, polyHash(text.slice(i, i + k))); // rolling == recomputing from scratch
}
console.log("ok");

C#

roll.cs

const long B = 131, M = 1_000_000_007;     // base > alphabet size; large prime modulus

// h(s) = s[0]*B^(k-1) + ... + s[k-1]  (mod M), via Horner's rule.
static long PolyHash(string s)
{
    long h = 0;
    foreach (char ch in s) h = (h * B + ch) % M;   // 1. shift left one "digit", add the new one
    return h;                                       //    h < M < 2^30, so h * B fits in a long
}

// Slide one place: drop outCh on the left, append inCh. top = B^(k-1) mod M.
static long Roll(long h, char outCh, char inCh, long top)
{
    h = (h - outCh * top % M + M) % M;              // 2. remove the leading term; + M keeps it >= 0
    return (h * B + inCh) % M;                      // 3. shift and add, exactly as in Horner
}

string text = "the quick brown fox";
int k = 5;
long top = 1;
for (int i = 0; i < k - 1; i++) top = top * B % M;
long hash = PolyHash(text[..k]);
for (int i = 1; i + k <= text.Length; i++)
{
    hash = Roll(hash, text[i - 1], text[i + k - 1], top);
    if (hash != PolyHash(text.Substring(i, k))) throw new Exception($"mismatch at {i}");
}
Console.WriteLine("ok");

Prefix hashes generalise this to any substring: store h[i] = hash of the first i characters and p[i] = Bⁱ. Then hash(s[l:r]) = h[r] − h[l]·p[r−l], just like a prefix sum with a shift.

Python

PrefixHash.py

class PrefixHash:
    """O(n) preprocessing, then the hash of any substring s[l:r] in O(1)."""

    def __init__(self, s: str, base: int = 131, mod: int = 1_000_000_007) -> None:
        self.mod = mod
        n = len(s)
        self.h = [0] * (n + 1)       # h[i] = hash of s[:i]
        self.p = [1] * (n + 1)       # p[i] = base^i mod m
        for i, ch in enumerate(s):
            self.h[i + 1] = (self.h[i] * base + ord(ch)) % mod   # 1. Horner over prefixes
            self.p[i + 1] = self.p[i] * base % mod

    def get(self, l: int, r: int) -> int:
        """Hash of s[l:r]: subtract the prefix shifted up by the window length."""
        return (self.h[r] - self.h[l] * self.p[r - l]) % self.mod  # 2. like prefix sums


if __name__ == "__main__":
    s = "abracadabra"
    ph = PrefixHash(s)
    assert ph.get(0, 4) == ph.get(7, 11)          # "abra" == "abra"
    assert ph.get(0, 4) != ph.get(1, 5)           # "abra" vs "brac"
    other = PrefixHash("cadab")
    assert ph.get(4, 9) == other.get(0, 5)        # same base and mod: comparable
    # 3. a hash match is evidence, not proof: confirm when it matters
    assert s[0:4] == s[7:11]
    print("ok")

TypeScript

PrefixHash.ts

import assert from "node:assert/strict";

/** O(n) preprocessing, then the hash of any substring s[l, r) in O(1). BigInt keeps it exact. */
export class PrefixHash {
  private readonly h: bigint[]; // h[i] = hash of s.slice(0, i)
  private readonly p: bigint[]; // p[i] = base^i mod m

  constructor(s: string, private readonly base = 131n, private readonly mod = 1_000_000_007n) {
    this.h = [0n];
    this.p = [1n];
    for (let i = 0; i < s.length; i++) {
      this.h.push((this.h[i] * base + BigInt(s.charCodeAt(i))) % mod); // 1. Horner over prefixes
      this.p.push((this.p[i] * base) % mod);
    }
  }

  /** Hash of s.slice(l, r): subtract the prefix shifted up by the window length. */
  get(l: number, r: number): bigint {
    const x = (this.h[r] - this.h[l] * this.p[r - l]) % this.mod; // 2. like prefix sums
    return x < 0n ? x + this.mod : x;
  }
}

const s = "abracadabra";
const ph = new PrefixHash(s);
assert.equal(ph.get(0, 4), ph.get(7, 11)); // "abra" == "abra"
assert.notEqual(ph.get(0, 4), ph.get(1, 5)); // "abra" vs "brac"
assert.equal(ph.get(4, 9), new PrefixHash("cadab").get(0, 5)); // same base and mod: comparable
assert.equal(s.slice(0, 4), s.slice(7, 11)); // 3. a hash match is evidence, not proof
console.log("ok");

C#

PrefixHash.cs

var s = "abracadabra";
var ph = new PrefixHash(s);
if (ph.Get(0, 4) != ph.Get(7, 11)) throw new Exception("abra == abra");
if (ph.Get(0, 4) == ph.Get(1, 5)) throw new Exception("abra != brac");
if (ph.Get(4, 9) != new PrefixHash("cadab").Get(0, 5)) throw new Exception("same base and mod: comparable");
if (s[0..4] != s[7..11]) throw new Exception("3. a hash match is evidence, not proof");
Console.WriteLine("ok");

// O(n) preprocessing, then the hash of any substring s[l..r) in O(1).
sealed class PrefixHash
{
    const long Base = 131, Mod = 1_000_000_007;   // Mod^2 < 2^63, so products fit in a long
    readonly long[] h, p;                          // h[i] = hash of s[..i], p[i] = Base^i mod Mod

    public PrefixHash(string s)
    {
        h = new long[s.Length + 1];
        p = new long[s.Length + 1];
        p[0] = 1;
        for (int i = 0; i < s.Length; i++)
        {
            h[i + 1] = (h[i] * Base + s[i]) % Mod;  // 1. Horner over prefixes
            p[i + 1] = p[i] * Base % Mod;
        }
    }

    // Hash of s[l..r): subtract the prefix shifted up by the window length.
    public long Get(int l, int r) => ((h[r] - h[l] * p[r - l]) % Mod + Mod) % Mod; // 2. like prefix sums
}

Overflow is the classic bug

h · B must not overflow before you reduce it. With M ≈ 10⁹ and B < 2³¹, the product fits in a signed 64-bit integer, so C# long is safe. JavaScript numbers are exact only up to 2⁵³, so h · B with h ≈ 10⁹ and B ≈ 10⁶ silently loses bits: use BigInt (as in the sample) or a smaller modulus. Python integers never overflow, but reduce anyway to keep numbers small and fast.

What it costs

	Time	Space
Hash one string of length k	O(k)	O(1)
Roll one step	O(1)	O(1)
All windows of length k in a text of length n	O(n)	O(1) rolling, O(n) to keep them
Prefix-hash table	O(n) build, O(1) per substring hash	O(n)
Rabin-Karp search	O(n + m) expected; O(n·m) worst case if many hits must be verified	O(1)

Choosing B and M, and how likely collisions are

• M: a large prime. Common choices: 10⁹ + 7, 998244353, or the Mersenne prime 2⁶¹ − 1 (needs 128-bit multiplication or a mulmod trick).
• B: larger than the alphabet (≥ 27 for lowercase letters, ≥ 256 for bytes), and not a multiple of M. Choosing B at random from [256, M−1] at startup defeats adversarial inputs designed for a known base (“anti-hash tests”).
• One comparison: two different strings of length up to k collide with probability at most about k / M for a random base (they agree only if B is a root of their difference polynomial, which has at most k roots).
• Many comparisons: by the birthday bound, among N distinct strings expect about N² / (2M) colliding pairs. With N = 10⁶ and M = 10⁹, that’s about 500 collisions. With M ≈ 2⁶¹, or two independent ~10⁹ moduli, it’s about 0.0002.

So: a single 10⁹ modulus is fine for one pattern against a text with verification, but not for “put a million substring hashes in a set and trust equality”. Use double hashing or 2⁶¹ − 1 there.

Variations you’ll meet

• Rabin-Karp for multiple patterns of the same length: put all pattern hashes in a set; one pass over the text.
• Substring equality queries: prefix hashes, O(1) each.
• Longest common prefix of two suffixes: binary search on the length with O(1) hash comparisons per probe: O(log n).
• Palindrome checks: forward and backward prefix hashes; a substring is a palindrome if both hashes agree.
• 2-D hashing: hash rows with one base, then columns of row hashes with another.
• Hashing for deduplication in systems (content-defined chunking in backup tools and rsync’s rolling checksum), where the same “slide and update” idea finds chunk boundaries.

Pitfalls

• Negative modulo. In JS, C# and Java, (-3) % 13 is -3. Add M before taking % again. Python’s % is always non-negative.
• Character value 0. If 'a' = 0, then "a", "aa" and "aaa" all hash to 0. Start at 1 or use code points.
• B ≡ 0 (mod M) (e.g. B = 26, M = 13): every term except the last vanishes. Keep B and M coprime.
• Forgetting top = B^(k−1), or recomputing it every step (O(k) each, defeating the point).
• Trusting equal hashes without verification when the number of comparisons is large (birthday bound above).
• Comparing hashes built with different B or M. They’re meaningless against each other.
• Precision in JS (see the caution above).

In the interview

• Say what you’re hashing and why: “I treat each length-k window as a base-B number mod M so I can slide it in O(1).”
• Write the roll formula carefully, including the non-negative fix.
• Address collisions unprompted: verify on match, or use a 2⁶¹ − 1 / double hash, and quote the birthday bound if you’re storing many hashes.
• Contrast with KMP: Rabin-Karp is simpler and generalises (many patterns, 2-D, substring equality), KMP has the worst-case guarantee.
• Expect: “what if an adversary chooses the input?” (random base), “what’s the probability of a false match?”, “can you do it without verification?”.

Check yourself

Check yourself

pick one

Digits as characters, B = 10, M = 1000. The window '123' has hash 123. Rolling one place to '234' gives…

A(123 − 1·100)·10 + 4 = 234B(123 − 1)·10 + 4 = 1224C123·10 + 4 = 1234

Check yourself

pick one

You store the hashes of 10⁶ distinct substrings in a set with a single modulus M ≈ 10⁹. About how many pairs collide by chance?

AAbout 0BAbout 500CAbout 10⁶

Check yourself

pick one

Your TypeScript rolling hash uses plain numbers with M = 10⁹ + 7 and B = 131, and hashes of equal windows sometimes differ. The likely bug?

Ah * B overflows 64 bitsB(h − out * top) % M can be negative, because JS % keeps the sign of the left operandCStrings must be converted to BigInt before hashing

Practice on your own

Classic exercises (not gym questions):

• Find all occurrences of any of several equal-length patterns in a text in one pass.
• Check whether two strings are rotations of each other using hashes of t + t.
• Longest common prefix of two suffixes of a string, using binary search and prefix hashes.
• Is there a palindromic substring of length k? Use forward and backward prefix hashes.
• Find a 2×2 pattern inside a character grid with 2-D rolling hashes.

Go deeper

• Introduction to Algorithms (CLRS), §32.2 “The Rabin-Karp algorithm”, including spurious hits and expected running time.
• cp-algorithms: string hashing, with prefix hashes, the collision probability and the birthday-paradox warning.
• Karp, R. M. and Rabin, M. O. (1987), “Efficient randomized pattern-matching algorithms”, IBM Journal of Research and Development 31(2).
• rsync technical report (Tridgell and Mackerras), the rolling checksum used in practice.

Related

String algorithmsKMP and the Z-function: worst-case linear matching.

Hash maps and setsWhere window hashes usually end up.

Sliding windowThe add-one, drop-one update rolling hashes rely on.

Prefix sumsSame 'subtract a prefix' trick, with a shift.