{"ID":5552841,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-03T21:22:07.242086766Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00204","arxiv_id":"2607.00204","title":"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 σ}{\\sqrt{\\log n}}+\\min(r,\\bar{r})\\log^εn)$ time for any $ε\u003e 0$, where $σ$ 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 $σ$ is small enough and $\\min(r,\\bar{r})=o(\\frac{n}{\\log^εn})$, yielding an asymptotic improvement over state-of-the-art algorithms. We also present a series of connected algorithmic results.","short_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 σ}{\\sqrt{\\log n}}+\\min(r,\\bar{r})\\log^εn)$...","url_abs":"https://arxiv.org/abs/2607.00204","url_pdf":"https://arxiv.org/pdf/2607.00204v1","authors":"[\"Hiroto Fujimaru\",\"Gonzalo Navarro\",\"Francisco Olivares\",\"Jakub Radoszewski\",\"Giuseppe Romana\",\"Cristian Urbina\"]","published":"2026-06-30T21:33:31Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}