Computing Smallest Suffixient Arrays in Sublinear Time

Abstract

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\dots n]$ in $O(\frac{n\log \ddot{I}ƒ}{\sqrt{\log n}}+\min (r,\bar{r}){\log }^{\hat{I}}\mu n)$ time for any $\hat{I}\mu >0$, where $\ddot{I}ƒ$ is the alphabet size of $T$ and $r$ and $\bar{r}$ are the numbers of equal-letter runs of the Burrows-Wheeler transforms of $T$ and its reverse $\overline{T}$, respectively. This time complexity becomes sublinear when $\ddot{I}ƒ$ is small enough and $\min (r,\bar{r})=o(\frac{n}{{\log }^{\hat{I}}\mu n})$, yielding an asymptotic improvement over state-of-the-art algorithms. We also present a series of connected algorithmic results.