823 Fundamental

Polynomial String Hashing

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Polynomial String Hashing" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Comparing strings character by character takes O(m) time. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Comparing strings character by character takes O(m) time. When you need to compare many substrings — checking if a string is a rotation of another, finding duplicate substrings, comparing all n^2 pairs of substrings — naive comparison becomes O(n^2 * m). Polynomial hashing reduces substring comparison to O(1) with O(n) preprocessing: compute prefix hashes, then any substring hash is (prefix[r] - prefix[l] * base^(r-l)) % mod. This enables O(n log n) string sorting, O(n) duplicate detection, and O(n log n) LCP (longest common prefix) binary search. It's the hash function behind rolling hash algorithms, string fingerprinting, and near-duplicate document detection.

🎯 Learning Outcomes

• Build prefix hash array h[i] = h[i-1]*base + s[i] for O(1) substring hash queries

• Precompute powers of base for the rolling subtraction formula

• Handle hash collisions using double hashing (two independent hash functions)

• Understand the polynomial hash formula and why prime moduli reduce collision probability

• Apply hashing to O(n log n) LCP computation via binary search + hash comparison

Code Example

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

(* Polynomial Rolling Hash in OCaml *)

let base = 31
let modp = 1_000_000_007

(* Build prefix hash array and powers for string s *)
(* h.(i) = hash of s[0..i-1], h.(0) = 0 *)
let build_hash (s : string) : int array * int array =
  let n = String.length s in
  let h = Array.make (n + 1) 0 in
  let pw = Array.make (n + 1) 1 in
  for i = 0 to n - 1 do
    let c = Char.code s.[i] - Char.code 'a' + 1 in
    h.(i + 1) <- (h.(i) * base + c) mod modp;
    pw.(i + 1) <- pw.(i) * base mod modp
  done;
  (h, pw)

(* Hash of s[l..r) (0-indexed, exclusive r) *)
let substring_hash (h : int array) (pw : int array) (l : int) (r : int) : int =
  (h.(r) - h.(l) * pw.(r - l) mod modp + modp * modp) mod modp

(* Rabin-Karp: find all occurrences of pattern in text *)
let rabin_karp (pattern : string) (text : string) : int list =
  let m = String.length pattern and n = String.length text in
  if m > n then []
  else begin
    let (ph, ppw) = build_hash pattern in
    let (th, tpw) = build_hash text in
    let pat_hash = substring_hash ph ppw 0 m in
    let results = ref [] in
    for i = 0 to n - m do
      let win_hash = substring_hash th tpw i (i + m) in
      (* Hash match: verify to avoid collisions *)
      if win_hash = pat_hash && String.sub text i m = pattern then
        results := i :: !results
    done;
    List.rev !results
  end

let () =
  let text = "abcabcabc" in
  let pattern = "abc" in
  let matches = rabin_karp pattern text in
  Printf.printf "rabin_karp(%S, %S) = [%s]\n" pattern text
    (String.concat "; " (List.map string_of_int matches));

  (* Show substring hashes equal for same content *)
  let s = "abcabc" in
  let (h, pw) = build_hash s in
  let h1 = substring_hash h pw 0 3 in
  let h2 = substring_hash h pw 3 6 in
  Printf.printf "hash('abc' at 0) = %d, hash('abc' at 3) = %d, equal=%b\n"
    h1 h2 (h1 = h2)

Key Differences

Aspect	Rust	OCaml
Arithmetic type	`u64` (64-bit unsigned)	`int` (63-bit signed) or `Int64`
Underflow prevention	Add `modulus^2` before subtract	Use absolute value or unsigned
Double hashing	Two `PolyHash` structs	Record with two hash arrays
Power precomputation	`Vec<u64>` with loop	`Array.init` or loop
Collision rate	`1/mod` per hash	Same; `1/(mod1*mod2)` for double
String access	`.as_bytes()[i]`	`Char.code (String.get s i)`

OCaml Approach

OCaml uses Int64 or native int (63-bit on 64-bit systems) for modular arithmetic. The prefix hash array is Array.make (n+1) 0 and powers array is Array.make (n+1) 1. OCaml's lsl, land, and mod operators handle modular arithmetic. The get function is a simple pure function over the arrays. For double hashing, a record { h1: int array; h2: int array; pw1: int array; pw2: int array } keeps both hash functions bundled. OCaml's polymorphic comparison avoids the need for custom hash combination.

Full Source

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

(* Polynomial Rolling Hash in OCaml *)

let base = 31
let modp = 1_000_000_007

(* Build prefix hash array and powers for string s *)
(* h.(i) = hash of s[0..i-1], h.(0) = 0 *)
let build_hash (s : string) : int array * int array =
  let n = String.length s in
  let h = Array.make (n + 1) 0 in
  let pw = Array.make (n + 1) 1 in
  for i = 0 to n - 1 do
    let c = Char.code s.[i] - Char.code 'a' + 1 in
    h.(i + 1) <- (h.(i) * base + c) mod modp;
    pw.(i + 1) <- pw.(i) * base mod modp
  done;
  (h, pw)

(* Hash of s[l..r) (0-indexed, exclusive r) *)
let substring_hash (h : int array) (pw : int array) (l : int) (r : int) : int =
  (h.(r) - h.(l) * pw.(r - l) mod modp + modp * modp) mod modp

(* Rabin-Karp: find all occurrences of pattern in text *)
let rabin_karp (pattern : string) (text : string) : int list =
  let m = String.length pattern and n = String.length text in
  if m > n then []
  else begin
    let (ph, ppw) = build_hash pattern in
    let (th, tpw) = build_hash text in
    let pat_hash = substring_hash ph ppw 0 m in
    let results = ref [] in
    for i = 0 to n - m do
      let win_hash = substring_hash th tpw i (i + m) in
      (* Hash match: verify to avoid collisions *)
      if win_hash = pat_hash && String.sub text i m = pattern then
        results := i :: !results
    done;
    List.rev !results
  end

let () =
  let text = "abcabcabc" in
  let pattern = "abc" in
  let matches = rabin_karp pattern text in
  Printf.printf "rabin_karp(%S, %S) = [%s]\n" pattern text
    (String.concat "; " (List.map string_of_int matches));

  (* Show substring hashes equal for same content *)
  let s = "abcabc" in
  let (h, pw) = build_hash s in
  let h1 = substring_hash h pw 0 3 in
  let h2 = substring_hash h pw 3 6 in
  Printf.printf "hash('abc' at 0) = %d, hash('abc' at 3) = %d, equal=%b\n"
    h1 h2 (h1 = h2)

Deep Comparison

OCaml vs Rust: String Hashing Poly

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 O(n log n) LCP array computation using binary search + polynomial hashing.

Use double hashing to find the longest duplicate substring with high confidence and no false positives.

Detect all anagram windows: substrings of length k that are permutations of a query string.

Implement string sorting using hash-based radix sort on hashed prefixes.

Measure empirical collision rate for single vs. double hashing on a large random string corpus.

Open Source Repos

functional-rust

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

Rust