Computing Smallest Suffixient Sets in Sublinear Time
Hiroto Fujimaru, Gonzalo Navarro, Francisco Olivares, Jakub Radoszewski,
Giuseppe Romana, and Cristian Urbina
A suffixient array is a novel data structure that, when combined with an index
providing direct access on a text T, allows us to answer a variety of pattern matching queries.
In this work, we show how to compute a smallest suffixient array for
T[1..n] in O((n log s)/sqrt(log n) + min(r,r^R) log^e n) time
for any e > 0, where s is the alphabet size of T and
r and r^R are the numbers of equal-letter runs of the Burrows-Wheeler transforms of T and
its reverse T^R, respectively. This time complexity becomes sublinear
when s is small enough and
min(r,r^R) = o(n/log^e n), yielding an asymptotic improvement over state-of-the-art algorithms. We also present a series of connected algorithmic results.