6 papers
Computing Smallest Suffixient Arrays in Sublinear Time
Hiroto Fujimaru, Gonzalo Navarro, Francisco Olivares +3
A suffixient array is a novel data structure that, when combined with an index providing direct access on a text , allows us to answer a variety of pattern matching queries. In…
Practical Linear-Time Computation of Smallest Suffixient Sets
Francisco Olivares, Gonzalo Navarro
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, t…
Optimal-Time Contextual Pattern Matching in Compressed Space
Gonzalo Navarro, Francisco Olivares
Contextual pattern matching is the task of, given a pattern , a context length , and a text , find all the distinct contexts in which occurs in , th…
Incongruity-sensitive access to highly compressed strings
Ferdinando Cicalese, Zsuzsanna Lipták, Travis Gagie +3
Random access to highly compressed strings -- represented by straight-line programs or Lempel-Ziv parses, for example -- is a well-studied topic. Random access to such strings in s…
Smallest Suffixient Sets: Effectiveness, Resilience, and Calculation
Hiroto Fujimaru, Gonzalo Navarro, Giuseppe Romana +1
A suffixient set is a novel combinatorial object that captures the essential information of repetitive strings in a way that, provided with a random access mechanism, supports vari…
Generalized Straight-Line Programs
Gonzalo Navarro, Francisco Olivares, Cristian Urbina
It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size.…