818 Advanced

Suffix Array

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Suffix Array" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. A suffix array enables lightning-fast substring search, counting occurrences, finding the longest repeated substring, and computing the longest common substring between two strings — all after O(n log n) preprocessing. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

A suffix array enables lightning-fast substring search, counting occurrences, finding the longest repeated substring, and computing the longest common substring between two strings — all after O(n log n) preprocessing. Without a suffix array or suffix tree, answering "how many times does pattern P appear in text T?" requires O(n*m) per query. With a suffix array, binary search answers each query in O(m log n). This powers full-text search engines, bioinformatics sequence analysis, data compression (BWT transform), and plagiarism detection tools. The suffix array is a space-efficient alternative to suffix trees that fits in O(n) integers.

🎯 Learning Outcomes

• Understand that a suffix array is a sorted array of starting indices of all suffixes of a string

• Implement the naive O(n^2 log n) construction using sort with suffix comparisons

• Recognize how binary search on a sorted suffix array answers substring queries in O(m log n)

• Learn how the LCP (Longest Common Prefix) array augments the suffix array for advanced queries

• Compare with suffix trees: suffix arrays use less memory but require more algorithmic sophistication

Code Example

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

(* Suffix Array — O(n log² n) prefix doubling + O(n) LCP (Kasai) *)

let build_sa s =
  let n    = String.length s in
  let sa   = Array.init n (fun i -> i) in
  let rank = Array.init n (fun i -> Char.code s.[i]) in
  let tmp  = Array.make n 0 in

  let gap = ref 1 in
  while !gap < n do
    let g = !gap in
    let cmp i j =
      let ri = rank.(i) and rj = rank.(j) in
      if ri <> rj then compare ri rj
      else
        let ri2 = if i + g < n then rank.(i + g) else (-1) in
        let rj2 = if j + g < n then rank.(j + g) else (-1) in
        compare ri2 rj2
    in
    Array.sort cmp sa;
    (* Update ranks *)
    tmp.(sa.(0)) <- 0;
    for i = 1 to n - 1 do
      tmp.(sa.(i)) <- tmp.(sa.(i-1)) + (if cmp sa.(i-1) sa.(i) = 0 then 0 else 1)
    done;
    Array.blit tmp 0 rank 0 n;
    gap := !gap * 2
  done;
  sa

(* Kasai's LCP array — O(n) *)
let build_lcp s sa =
  let n    = String.length s in
  let rank = Array.make n 0 in
  Array.iteri (fun i v -> rank.(v) <- i) sa;
  let lcp  = Array.make n 0 in
  let k    = ref 0 in
  for i = 0 to n - 1 do
    if rank.(i) > 0 then begin
      let j = sa.(rank.(i) - 1) in
      while i + !k < n && j + !k < n && s.[i + !k] = s.[j + !k] do
        incr k
      done;
      lcp.(rank.(i)) <- !k;
      if !k > 0 then decr k
    end
  done;
  lcp

let sa_search s sa pattern =
  let n = Array.length sa in
  let m = String.length pattern in
  (* Binary search: left bound *)
  let lo = ref 0 and hi = ref n in
  while !lo < !hi do
    let mid = (!lo + !hi) / 2 in
    if String.sub s sa.(mid) (min m (String.length s - sa.(mid))) < pattern then
      lo := mid + 1
    else hi := mid
  done;
  let left = !lo in
  hi := n;
  while !lo < !hi do
    let mid = (!lo + !hi) / 2 in
    let suf = String.sub s sa.(mid) (min m (String.length s - sa.(mid))) in
    if suf <= pattern then lo := mid + 1
    else hi := mid
  done;
  (* Collect positions *)
  let positions = Array.sub sa left (!lo - left) in
  Array.sort compare positions;
  Array.to_list positions

let () =
  let s  = "banana" in
  let sa = build_sa s in
  let lcp = build_lcp s sa in
  Printf.printf "String: %S\n" s;
  Printf.printf "SA:  [%s]\n" (String.concat "," (Array.to_list (Array.map string_of_int sa)));
  Printf.printf "LCP: [%s]\n" (String.concat "," (Array.to_list (Array.map string_of_int lcp)));
  Printf.printf "Suffixes in order:\n";
  Array.iter (fun i -> Printf.printf "  %d: %S\n" i (String.sub s i (String.length s - i))) sa;
  let pos = sa_search s sa "an" in
  Printf.printf "Search 'an': [%s]\n"
    (String.concat "," (List.map string_of_int pos))

Key Differences

Aspect	Rust	OCaml
Suffix comparison	`bytes[a..].cmp(&bytes[b..])`	`String.sub s a len \|> compare`
Sort	`.sort_by()` with closure	`Array.sort` with comparison function
Construction complexity	Naive O(n^2 log n)	Same for naive; SA-IS for O(n)
Binary search	`partition_point` for range	Manual bisection or library
Memory	`Vec<usize>` — cache-friendly	`int array` — GC-managed
Unicode	Byte-level (ASCII assumed)	`Uchar.t array` for full Unicode

OCaml Approach

OCaml builds the suffix array with Array.init n (fun i -> i) then Array.sort with a comparator using String.sub for suffix extraction. The naive approach is functionally clean: Array.sort (fun a b -> compare (String.sub s a n) (String.sub s b n)) sa. More efficient O(n log^2 n) doubling algorithms use Array.map to rank suffixes and iteratively refine. OCaml's String.compare for lexicographic order maps directly to the comparison needed. For binary search, Array.binary_search (in some libraries) or manual bisection applies.

Full Source

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

(* Suffix Array — O(n log² n) prefix doubling + O(n) LCP (Kasai) *)

let build_sa s =
  let n    = String.length s in
  let sa   = Array.init n (fun i -> i) in
  let rank = Array.init n (fun i -> Char.code s.[i]) in
  let tmp  = Array.make n 0 in

  let gap = ref 1 in
  while !gap < n do
    let g = !gap in
    let cmp i j =
      let ri = rank.(i) and rj = rank.(j) in
      if ri <> rj then compare ri rj
      else
        let ri2 = if i + g < n then rank.(i + g) else (-1) in
        let rj2 = if j + g < n then rank.(j + g) else (-1) in
        compare ri2 rj2
    in
    Array.sort cmp sa;
    (* Update ranks *)
    tmp.(sa.(0)) <- 0;
    for i = 1 to n - 1 do
      tmp.(sa.(i)) <- tmp.(sa.(i-1)) + (if cmp sa.(i-1) sa.(i) = 0 then 0 else 1)
    done;
    Array.blit tmp 0 rank 0 n;
    gap := !gap * 2
  done;
  sa

(* Kasai's LCP array — O(n) *)
let build_lcp s sa =
  let n    = String.length s in
  let rank = Array.make n 0 in
  Array.iteri (fun i v -> rank.(v) <- i) sa;
  let lcp  = Array.make n 0 in
  let k    = ref 0 in
  for i = 0 to n - 1 do
    if rank.(i) > 0 then begin
      let j = sa.(rank.(i) - 1) in
      while i + !k < n && j + !k < n && s.[i + !k] = s.[j + !k] do
        incr k
      done;
      lcp.(rank.(i)) <- !k;
      if !k > 0 then decr k
    end
  done;
  lcp

let sa_search s sa pattern =
  let n = Array.length sa in
  let m = String.length pattern in
  (* Binary search: left bound *)
  let lo = ref 0 and hi = ref n in
  while !lo < !hi do
    let mid = (!lo + !hi) / 2 in
    if String.sub s sa.(mid) (min m (String.length s - sa.(mid))) < pattern then
      lo := mid + 1
    else hi := mid
  done;
  let left = !lo in
  hi := n;
  while !lo < !hi do
    let mid = (!lo + !hi) / 2 in
    let suf = String.sub s sa.(mid) (min m (String.length s - sa.(mid))) in
    if suf <= pattern then lo := mid + 1
    else hi := mid
  done;
  (* Collect positions *)
  let positions = Array.sub sa left (!lo - left) in
  Array.sort compare positions;
  Array.to_list positions

let () =
  let s  = "banana" in
  let sa = build_sa s in
  let lcp = build_lcp s sa in
  Printf.printf "String: %S\n" s;
  Printf.printf "SA:  [%s]\n" (String.concat "," (Array.to_list (Array.map string_of_int sa)));
  Printf.printf "LCP: [%s]\n" (String.concat "," (Array.to_list (Array.map string_of_int lcp)));
  Printf.printf "Suffixes in order:\n";
  Array.iter (fun i -> Printf.printf "  %d: %S\n" i (String.sub s i (String.length s - i))) sa;
  let pos = sa_search s sa "an" in
  Printf.printf "Search 'an': [%s]\n"
    (String.concat "," (List.map string_of_int pos))

Deep Comparison

OCaml vs Rust: Suffix Array

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 the LCP array using Kasai's algorithm and use it to find the longest repeated substring.

Add a search_range function returning all positions where a pattern occurs using the LCP array.

Implement the O(n log^2 n) suffix array construction using the doubling technique.

Use the suffix array to find the longest common substring of two strings by concatenating with a sentinel.

Benchmark suffix array binary search against a simple sliding window search for varying pattern lengths.

Open Source Repos

functional-rust

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

Rust