{"ID":5438570,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T01:40:09.565152011Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31034","arxiv_id":"2606.31034","title":"Practical Linear-Time Computation of Smallest Suffixient Sets","abstract":"Suffixient arrays are recent structures that have attracted attention because they offer relevant pattern matching functionality in less asymptotic space than the Run-Length BWT, the de-facto standard to index highly repetitive string collections. Various algorithms exist for building them from the suffix array data structures. We present the first construction algorithm that is (i) linear-time, (ii) one-pass over the structures, and (iii) implemented and practical. This makes the construction particularly useful on large text collections, which we demonstrate empirically by showing that it dominates the space/time tradeoff map of the implemented constructions.","short_abstract":"Suffixient arrays are recent structures that have attracted attention because they offer relevant pattern matching functionality in less asymptotic space than the Run-Length BWT, the de-facto standard to index highly repetitive string collections. Various algorithms exist for building them from the suffix array data st...","url_abs":"https://arxiv.org/abs/2606.31034","url_pdf":"https://arxiv.org/pdf/2606.31034v1","authors":"[\"Francisco Olivares\",\"Gonzalo Navarro\"]","published":"2026-06-30T02:05:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}