816 Fundamental

Rabin-Karp Rolling Hash

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Rabin-Karp Rolling Hash" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Finding multiple patterns in a text, or detecting plagiarism across documents, requires more than single-pattern search. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Finding multiple patterns in a text, or detecting plagiarism across documents, requires more than single-pattern search. Rabin-Karp solves this using polynomial hashing: compute a hash for each window of text equal in size to the pattern, and compare hashes rather than characters. The rolling hash property means each step takes O(1) — subtract the contribution of the outgoing character and add the incoming one. This enables searching for k patterns simultaneously in O(n + k*m) expected time. Real-world uses: duplicate code detection, plagiarism detection, DNA fingerprinting, and detecting repeated substrings in large files.

🎯 Learning Outcomes

• Understand polynomial rolling hash: hash = (c0*b^(m-1) + c1*b^(m-2) + ... + c(m-1)) mod p

• Implement O(1) hash update by rolling: subtract old char contribution, multiply, add new char

• Handle hash collisions with character-level verification (spurious hits)

• Recognize Rabin-Karp's advantage for multi-pattern search vs single-pattern algorithms

• Learn the importance of choosing prime modulus and base to minimize collision probability

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Rabin-Karp Rolling Hash — O(n+m) expected *)

let base  = 256
let prime = 1_000_000_007

let rabin_karp text pattern =
  let n = String.length text in
  let m = String.length pattern in
  if m = 0 then []
  else if m > n then []
  else begin
    (* Compute base^(m-1) mod prime *)
    let pow = ref 1 in
    for _ = 1 to m - 1 do
      pow := (!pow * base) mod prime
    done;

    (* Compute initial hashes *)
    let hash_p = ref 0 in
    let hash_t = ref 0 in
    for i = 0 to m - 1 do
      hash_p := (!hash_p * base + Char.code pattern.[i]) mod prime;
      hash_t := (!hash_t * base + Char.code text.[i])    mod prime
    done;

    let matches = ref [] in
    for i = 0 to n - m do
      if !hash_t = !hash_p then begin
        (* Verify (avoid false positives) *)
        let ok = ref true in
        for j = 0 to m - 1 do
          if text.[i+j] <> pattern.[j] then ok := false
        done;
        if !ok then matches := i :: !matches
      end;
      (* Roll hash *)
      if i < n - m then begin
        hash_t := ((!hash_t - Char.code text.[i] * !pow mod prime + prime) * base
                   + Char.code text.[i + m]) mod prime
      end
    done;
    List.rev !matches
  end

let () =
  let text = "ABCDABABCDABCDAB" in
  let pat  = "ABCD" in
  Printf.printf "Text:    %S\n" text;
  Printf.printf "Pattern: %S\n" pat;
  Printf.printf "Matches: [%s]\n"
    (String.concat "; " (List.map string_of_int (rabin_karp text pat)));

  let m2 = rabin_karp "aaabaaabaa" "aab" in
  Printf.printf "\"aab\" in \"aaabaaabaa\": [%s]\n"
    (String.concat "; " (List.map string_of_int m2))

Key Differences

Aspect	Rust	OCaml
Arithmetic	`u64` with explicit `% modulus`	`int` (63-bit) with `mod`
Byte access	`.as_bytes()[i]`	`Char.code (String.get s i)`
Hash state	Mutable variable in loop	Threaded through recursion
Multi-pattern	`HashMap<u64, Vec<Pattern>>`	`Hashtbl` keyed by hash
Overflow risk	None with `u64 % modulus`	Rare on 64-bit, possible on 32-bit
False positives	Verified with `==` comparison	Same character-level check

OCaml Approach

OCaml implements rolling hash with int arithmetic, relying on its 63-bit native integers to avoid overflow on most platforms. The Char.code function extracts byte values. The rolling hash state threads through a tail-recursive function rather than a loop, maintaining immutability. OCaml's List.rev collects match positions in reverse and reverses at the end. For multi-pattern Rabin-Karp, a Hashtbl maps hash values to pattern lists, checking all patterns with matching hashes.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Rabin-Karp Rolling Hash — O(n+m) expected *)

let base  = 256
let prime = 1_000_000_007

let rabin_karp text pattern =
  let n = String.length text in
  let m = String.length pattern in
  if m = 0 then []
  else if m > n then []
  else begin
    (* Compute base^(m-1) mod prime *)
    let pow = ref 1 in
    for _ = 1 to m - 1 do
      pow := (!pow * base) mod prime
    done;

    (* Compute initial hashes *)
    let hash_p = ref 0 in
    let hash_t = ref 0 in
    for i = 0 to m - 1 do
      hash_p := (!hash_p * base + Char.code pattern.[i]) mod prime;
      hash_t := (!hash_t * base + Char.code text.[i])    mod prime
    done;

    let matches = ref [] in
    for i = 0 to n - m do
      if !hash_t = !hash_p then begin
        (* Verify (avoid false positives) *)
        let ok = ref true in
        for j = 0 to m - 1 do
          if text.[i+j] <> pattern.[j] then ok := false
        done;
        if !ok then matches := i :: !matches
      end;
      (* Roll hash *)
      if i < n - m then begin
        hash_t := ((!hash_t - Char.code text.[i] * !pow mod prime + prime) * base
                   + Char.code text.[i + m]) mod prime
      end
    done;
    List.rev !matches
  end

let () =
  let text = "ABCDABABCDABCDAB" in
  let pat  = "ABCD" in
  Printf.printf "Text:    %S\n" text;
  Printf.printf "Pattern: %S\n" pat;
  Printf.printf "Matches: [%s]\n"
    (String.concat "; " (List.map string_of_int (rabin_karp text pat)));

  let m2 = rabin_karp "aaabaaabaa" "aab" in
  Printf.printf "\"aab\" in \"aaabaaabaa\": [%s]\n"
    (String.concat "; " (List.map string_of_int m2))

Deep Comparison

OCaml vs Rust: Rabin Karp Rolling Hash

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement 2D Rabin-Karp to find a pattern matrix inside a larger text matrix.

Add multi-pattern support: search for all patterns in a set simultaneously in a single pass.

Measure false positive rate empirically with random text and various base/modulus choices.

Compare performance with Boyer-Moore on long text with many short patterns of equal length.

Handle Unicode by hashing on code points rather than bytes and verify correctness.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust