786 Intermediate

786-longest-common-subsequence — Longest Common Subsequence

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "786-longest-common-subsequence — Longest Common Subsequence" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. The Longest Common Subsequence (LCS) problem finds the longest sequence of characters common to two strings (not necessarily contiguous). Key difference from OCaml: 1. **Array access**: Rust's `Vec<Vec<usize>>` indexing with `dp[i][j]`; OCaml's `dp.(i).(j)` — syntactically different but equivalent.

Tutorial

The Problem

The Longest Common Subsequence (LCS) problem finds the longest sequence of characters common to two strings (not necessarily contiguous). It is the foundation of diff tools (used in Git, patch, and code review), DNA sequence alignment (BLAST, ClustalW), and plagiarism detection. The classic O(mn) DP solution by Hirschberg (1975) fills an m×n table comparing characters.

🎯 Learning Outcomes

• Fill a 2D DP table dp[i][j] = LCS length of a[:i] and b[:j]

• Apply the recurrence: match increases by 1, mismatch takes max of adjacent cells

• Reconstruct the actual LCS string by backtracking through the table

• Understand the relationship between LCS and edit distance (Levenshtein)

• See how LCS extends to multiple sequences (3-way LCS) at higher complexity

Code Example

#![allow(clippy::all)]
//! # Longest Common Subsequence

pub fn lcs(a: &str, b: &str) -> usize {
    let (m, n) = (a.len(), b.len());
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1
            } else {
                dp[i - 1][j].max(dp[i][j - 1])
            };
        }
    }
    dp[m][n]
}

pub fn lcs_string(a: &str, b: &str) -> String {
    let (m, n) = (a.len(), b.len());
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1
            } else {
                dp[i - 1][j].max(dp[i][j - 1])
            };
        }
    }

    let mut result = Vec::new();
    let (mut i, mut j) = (m, n);
    while i > 0 && j > 0 {
        if a[i - 1] == b[j - 1] {
            result.push(a[i - 1]);
            i -= 1;
            j -= 1;
        } else if dp[i - 1][j] > dp[i][j - 1] {
            i -= 1;
        } else {
            j -= 1;
        }
    }
    result.iter().rev().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lcs() {
        assert_eq!(lcs("ABCDGH", "AEDFHR"), 3);
    }
    #[test]
    fn test_lcs_string() {
        assert_eq!(lcs_string("ABCDGH", "AEDFHR"), "ADH");
    }
    #[test]
    fn test_empty() {
        assert_eq!(lcs("", "ABC"), 0);
    }
    #[test]
    fn test_identical() {
        assert_eq!(lcs("ABC", "ABC"), 3);
    }
}

(* LCS: classic DP with backtracking in OCaml *)

(* ── Recursive with memoisation ───────────────────────────────────────────────── *)
let lcs_memo s1 s2 =
  let n = String.length s1 and m = String.length s2 in
  let memo = Hashtbl.create 256 in
  let rec dp i j =
    if i = 0 || j = 0 then 0
    else match Hashtbl.find_opt memo (i, j) with
    | Some v -> v
    | None ->
      let v =
        if s1.[i-1] = s2.[j-1] then 1 + dp (i-1) (j-1)
        else max (dp (i-1) j) (dp i (j-1))
      in
      Hashtbl.replace memo (i, j) v;
      v
  in
  dp n m

(* ── Tabulation + backtrack ────────────────────────────────────────────────────── *)
let lcs_tab s1 s2 =
  let n = String.length s1 and m = String.length s2 in
  let dp = Array.make_matrix (n+1) (m+1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      dp.(i).(j) <-
        if s1.[i-1] = s2.[j-1] then dp.(i-1).(j-1) + 1
        else max dp.(i-1).(j) dp.(i).(j-1)
    done
  done;
  (* Backtrack *)
  let buf = Buffer.create 16 in
  let i = ref n and j = ref m in
  while !i > 0 && !j > 0 do
    if s1.[!i - 1] = s2.[!j - 1] then begin
      Buffer.add_char buf s1.[!i - 1];
      decr i; decr j
    end else if dp.(!i-1).(!j) > dp.(!i).(!j-1) then decr i
    else decr j
  done;
  let s = Buffer.contents buf in
  (* reverse *)
  String.init (String.length s) (fun i -> s.[String.length s - 1 - i])

let () =
  let s1 = "ABCBDAB" and s2 = "BDCAB" in
  Printf.printf "LCS length (memo): %d\n"  (lcs_memo s1 s2);
  Printf.printf "LCS string (tab):  %S\n"  (lcs_tab s1 s2);
  (* Another example *)
  let a = "AGGTAB" and b = "GXTXAYB" in
  Printf.printf "LCS(%S, %S) = %S\n" a b (lcs_tab a b)

Key Differences

Array access: Rust's Vec<Vec<usize>> indexing with dp[i][j]; OCaml's dp.(i).(j) — syntactically different but equivalent.

String iteration: Rust collects chars() into a Vec<char> for indexed access; OCaml uses Bytes.get on a Bytes.of_string copy.

Backtracking: Both use iterative backtracking with while loops — identical structure.

Space optimization: Hirschberg's O(n) space LCS algorithm is expressible in both languages; neither standard library includes it.

OCaml Approach

OCaml implements LCS with the same 2D array approach. let dp = Array.make_matrix (m+1) (n+1) 0 in .... Backtracking uses a recursive function that pattern-matches on the dp values. OCaml's List.rev is often used to accumulate characters in reverse during backtracking. The Diff library wraps LCS for line-level diff computation similar to git diff.

Full Source

#![allow(clippy::all)]
//! # Longest Common Subsequence

pub fn lcs(a: &str, b: &str) -> usize {
    let (m, n) = (a.len(), b.len());
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1
            } else {
                dp[i - 1][j].max(dp[i][j - 1])
            };
        }
    }
    dp[m][n]
}

pub fn lcs_string(a: &str, b: &str) -> String {
    let (m, n) = (a.len(), b.len());
    let a: Vec<char> = a.chars().collect();
    let b: Vec<char> = b.chars().collect();
    let mut dp = vec![vec![0; n + 1]; m + 1];

    for i in 1..=m {
        for j in 1..=n {
            dp[i][j] = if a[i - 1] == b[j - 1] {
                dp[i - 1][j - 1] + 1
            } else {
                dp[i - 1][j].max(dp[i][j - 1])
            };
        }
    }

    let mut result = Vec::new();
    let (mut i, mut j) = (m, n);
    while i > 0 && j > 0 {
        if a[i - 1] == b[j - 1] {
            result.push(a[i - 1]);
            i -= 1;
            j -= 1;
        } else if dp[i - 1][j] > dp[i][j - 1] {
            i -= 1;
        } else {
            j -= 1;
        }
    }
    result.iter().rev().collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lcs() {
        assert_eq!(lcs("ABCDGH", "AEDFHR"), 3);
    }
    #[test]
    fn test_lcs_string() {
        assert_eq!(lcs_string("ABCDGH", "AEDFHR"), "ADH");
    }
    #[test]
    fn test_empty() {
        assert_eq!(lcs("", "ABC"), 0);
    }
    #[test]
    fn test_identical() {
        assert_eq!(lcs("ABC", "ABC"), 3);
    }
}

(* LCS: classic DP with backtracking in OCaml *)

(* ── Recursive with memoisation ───────────────────────────────────────────────── *)
let lcs_memo s1 s2 =
  let n = String.length s1 and m = String.length s2 in
  let memo = Hashtbl.create 256 in
  let rec dp i j =
    if i = 0 || j = 0 then 0
    else match Hashtbl.find_opt memo (i, j) with
    | Some v -> v
    | None ->
      let v =
        if s1.[i-1] = s2.[j-1] then 1 + dp (i-1) (j-1)
        else max (dp (i-1) j) (dp i (j-1))
      in
      Hashtbl.replace memo (i, j) v;
      v
  in
  dp n m

(* ── Tabulation + backtrack ────────────────────────────────────────────────────── *)
let lcs_tab s1 s2 =
  let n = String.length s1 and m = String.length s2 in
  let dp = Array.make_matrix (n+1) (m+1) 0 in
  for i = 1 to n do
    for j = 1 to m do
      dp.(i).(j) <-
        if s1.[i-1] = s2.[j-1] then dp.(i-1).(j-1) + 1
        else max dp.(i-1).(j) dp.(i).(j-1)
    done
  done;
  (* Backtrack *)
  let buf = Buffer.create 16 in
  let i = ref n and j = ref m in
  while !i > 0 && !j > 0 do
    if s1.[!i - 1] = s2.[!j - 1] then begin
      Buffer.add_char buf s1.[!i - 1];
      decr i; decr j
    end else if dp.(!i-1).(!j) > dp.(!i).(!j-1) then decr i
    else decr j
  done;
  let s = Buffer.contents buf in
  (* reverse *)
  String.init (String.length s) (fun i -> s.[String.length s - 1 - i])

let () =
  let s1 = "ABCBDAB" and s2 = "BDCAB" in
  Printf.printf "LCS length (memo): %d\n"  (lcs_memo s1 s2);
  Printf.printf "LCS string (tab):  %S\n"  (lcs_tab s1 s2);
  (* Another example *)
  let a = "AGGTAB" and b = "GXTXAYB" in
  Printf.printf "LCS(%S, %S) = %S\n" a b (lcs_tab a b)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lcs() {
        assert_eq!(lcs("ABCDGH", "AEDFHR"), 3);
    }
    #[test]
    fn test_lcs_string() {
        assert_eq!(lcs_string("ABCDGH", "AEDFHR"), "ADH");
    }
    #[test]
    fn test_empty() {
        assert_eq!(lcs("", "ABC"), 0);
    }
    #[test]
    fn test_identical() {
        assert_eq!(lcs("ABC", "ABC"), 3);
    }
}

Deep Comparison

OCaml vs Rust: Longest Common Subsequence

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 lcs_diff(a: &[&str], b: &[&str]) -> Vec<DiffOp> that returns a diff as a list of Keep, Insert, and Delete operations — the basis for git diff.

Implement the space-optimized O(m+n) space LCS using Hirschberg's divide-and-conquer algorithm.

Extend to three sequences: lcs3(a, b, c) using a 3D DP table, and verify it on biological sequences.

Open Source Repos

functional-rust

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

Rust