MEM-finding with run-length compressed strings

2026/08/02 by Paola Bonizzoni, Davide Cozzi, Travis Gagie +2
Computer Science · #cs.DS

paper · pdf

arxiv created 2026/08/02 · arxiv updated 2026/08/04

Abstract

We show how to store a text T [1..n] consisting of ρ_T runs in O (ρ_T + χ) space, where χ is the size of the smallest suffixient set for T, such that when we are given a pattern P [1..m] consisting of ρ_P runs we can find the maximal exact matches (MEMs) of P with respect to T in O (ρ_P log m) time plus constant time for each edge we would fully or partially descend in the suffix tree for T while finding those MEMs. We then adapt and optimize our result to finding set-maximal exact matches (SMEMs) of query haplotypes with respect to stored haplotype panels.

Citations

• On the near-tightness of χ≤ 2r: a general σ-ary construction and a binary case via LFSRs
• Compressing Suffix Trees by Path Decompositions
• An Optimal-Time RLBWT Construction in BWT-runs Bounded Space
• In-Place Sparse Suffix Sorting
• Succinct Representations of Permutations and Functions
• Fast Prefix Search in Little Space, with Applications