textmetrics/lcs

Longest Common Subsequence helpers.

Generic over any equality-comparable list type (List(t)); pre-split strings via gleam/string.to_graphemes for grapheme-level results. This module performs no Unicode normalization.

Values

length

</>

pub fn length(a: List(t), b: List(t)) -> Int

Length of a longest common subsequence of a and b.

Time O(m·n), space O(m + n). Returns 0 when either input is empty.

Note: this name shadows gleam/list.length if both are imported unqualified (import textmetrics/lcs.{length}). Prefer the qualified lcs.length(...) form to avoid the conflict.

sequence

</>

pub fn sequence(a: List(t), b: List(t)) -> List(t)

One longest common subsequence of a and b.

When multiple equally-long subsequences exist, this implementation returns the one preferring upward backtracking on ties — callers should treat the choice as implementation-defined and only rely on length(sequence(a, b)) == length(a, b).

Time O(m·n), space O(m·n) (full DP matrix retained for backtracking).