819 Fundamental

Z-Algorithm String Matching

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Z-Algorithm String Matching" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. The Z-algorithm computes, for each position in a string, the length of the longest substring starting at that position that is also a prefix of the whole string. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The Z-algorithm computes, for each position in a string, the length of the longest substring starting at that position that is also a prefix of the whole string. This Z-array answers pattern matching questions directly: concatenate pattern + "$" + text, compute the Z-array, and any position where Z[i] equals the pattern length is a match. The algorithm runs in O(n) time and O(n) space, making it a linear alternative to KMP with a simpler conceptual model. It powers prefix-related string queries in competitive programming, bioinformatics repeat analysis, and text compression preprocessing.

🎯 Learning Outcomes

• Understand the Z-box (l, r) maintenance: a window tracking the rightmost known matching prefix

• Implement O(1) amortized extension using the existing Z-box to skip recomputation

• Recognize the pattern matching reduction: P + $ + T → find positions where Z[i] == |P|

• Learn the difference from KMP failure function: Z measures prefix matches at each position directly

• Apply Z-array to: string periods, pattern counting, lexicographically smallest rotation

Code Example

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

(* Z-Algorithm in OCaml — functional style with Array *)

(* Build Z-array: Z.(i) = length of longest match with prefix of s starting at i *)
let z_array (s : string) : int array =
  let n = String.length s in
  let z = Array.make n 0 in
  let chars = Array.init n (String.get s) in
  z.(0) <- n;
  let l = ref 0 and r = ref 0 in
  for i = 1 to n - 1 do
    if i < !r then
      z.(i) <- min (z.(i - !l)) (!r - i);
    while i + z.(i) < n && chars.(z.(i)) = chars.(i + z.(i)) do
      z.(i) <- z.(i) + 1
    done;
    if i + z.(i) > !r then begin
      l := i;
      r := i + z.(i)
    end
  done;
  z

(* Pattern search: returns list of 0-based match positions in text *)
let z_search (pattern : string) (text : string) : int list =
  let m = String.length pattern in
  let combined = pattern ^ "$" ^ text in
  let z = z_array combined in
  let n = String.length combined in
  (* Positions in combined where Z = m correspond to match starts in text *)
  let results = ref [] in
  for i = m + 1 to n - 1 do
    if z.(i) = m then
      results := (i - m - 1) :: !results
  done;
  List.rev !results

let () =
  let text = "aabxaabxaab" in
  let pattern = "aab" in
  let matches = z_search pattern text in
  Printf.printf "Pattern '%s' found at positions: " pattern;
  List.iter (fun p -> Printf.printf "%d " p) matches;
  print_newline ();

  (* Demonstrate Z-array directly *)
  let s = "aabxaa" in
  let z = z_array s in
  Printf.printf "Z-array of '%s': " s;
  Array.iter (fun v -> Printf.printf "%d " v) z;
  print_newline ()

Key Differences

Aspect	Rust	OCaml
Input type	`&[u8]` — byte slice	`bytes` or `string`
Z-box state	Two `usize` variables	`int ref` or threaded recursion
Concatenation	`[pattern, b'$', text].concat()`	`Bytes.concat`
Bound checks	Debug-mode auto-checks	`Bytes.get` raises exception
Result filter	`enumerate().filter()`	`Array.to_seq \\|> Seq.filter_mapi`
Separator byte	Must not appear in input	Same constraint

OCaml Approach

OCaml implements the Z-function with mutable int ref for l and r, or threads them through a tail-recursive loop. Bytes.get provides O(1) character access. The Array.make n 0 creates the Z-array. OCaml's pattern matching on the Z-box condition i < r maps cleanly to if i < !r then. For string matching, Bytes.concat Bytes.empty [pattern; sep; text] creates the concatenated input. The result scan Array.to_seq |> Seq.filter_mapi finds positions where Z equals pattern length.

Full Source

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

(* Z-Algorithm in OCaml — functional style with Array *)

(* Build Z-array: Z.(i) = length of longest match with prefix of s starting at i *)
let z_array (s : string) : int array =
  let n = String.length s in
  let z = Array.make n 0 in
  let chars = Array.init n (String.get s) in
  z.(0) <- n;
  let l = ref 0 and r = ref 0 in
  for i = 1 to n - 1 do
    if i < !r then
      z.(i) <- min (z.(i - !l)) (!r - i);
    while i + z.(i) < n && chars.(z.(i)) = chars.(i + z.(i)) do
      z.(i) <- z.(i) + 1
    done;
    if i + z.(i) > !r then begin
      l := i;
      r := i + z.(i)
    end
  done;
  z

(* Pattern search: returns list of 0-based match positions in text *)
let z_search (pattern : string) (text : string) : int list =
  let m = String.length pattern in
  let combined = pattern ^ "$" ^ text in
  let z = z_array combined in
  let n = String.length combined in
  (* Positions in combined where Z = m correspond to match starts in text *)
  let results = ref [] in
  for i = m + 1 to n - 1 do
    if z.(i) = m then
      results := (i - m - 1) :: !results
  done;
  List.rev !results

let () =
  let text = "aabxaabxaab" in
  let pattern = "aab" in
  let matches = z_search pattern text in
  Printf.printf "Pattern '%s' found at positions: " pattern;
  List.iter (fun p -> Printf.printf "%d " p) matches;
  print_newline ();

  (* Demonstrate Z-array directly *)
  let s = "aabxaa" in
  let z = z_array s in
  Printf.printf "Z-array of '%s': " s;
  Array.iter (fun v -> Printf.printf "%d " v) z;
  print_newline ()

Deep Comparison

OCaml vs Rust: Z Algorithm

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

Use the Z-array to find the shortest period of a string (smallest k such that the string is made of repeating k-length prefix).

Find all occurrences of a pattern in text and return start/end pairs using the Z-function approach.

Implement lexicographically smallest rotation: find i that minimizes s[i..] + s[..i].

Compare Z-algorithm and KMP on identical inputs and verify they produce consistent results.

Use the Z-array to count distinct substrings that are prefixes of the string.

Open Source Repos

functional-rust

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

Rust