Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes
2026-07-06 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to build and update special sets of suffixes called smallest suffixient sets and how to find the longest repeating suffix in a string as new characters arrive, doing so in a space-efficient (compressed) way. They offer new methods that balance memory use and processing speed better than before, especially for repetitive texts. The paper also shows that these problems unavoidably need a linear amount of memory in the worst case. Their algorithms improve on previous work by reducing time per character and guaranteeing worst-case performance, not just average. Overall, the authors present the first compressed-space online algorithms with strong theoretical guarantees.
smallest suffixient setlongest repeating suffix (LRS)online algorithmscompressed spaceBurrows-Wheeler transformrunsstring algorithmstime-space trade-offdeterministic algorithmsworst-case complexity
Authors
Paola Bonizzoni, Younan Gao, Dominik Köppl, Gregory Kucherov
Abstract
We revisit the online construction of \emph{smallest suffixient sets} and the online computation of the \emph{longest repeating suffix} (LRS). We give the first compressed-space online construction of smallest suffixient sets, and present two space-time trade-offs for both problems: $O(r\log n+n)$ bits of working space and $O(\log^2 n/\log \log n)$ worst-case time per character, and $O(r\log n+n \log \log n)$ bits of working space and $O((\log n/\log \log n)^2)$ worst-case time per character. Here, $r$ is the number of runs in the Burrows-Wheeler transform of the reverse of $T[1..n]$. In particular, for highly repetitive texts satisfying $r=O(n/\log n)$, the first trade-off uses $O(n)$ bits of working space, while the second uses $O(n\log\log n)$ bits. We also prove that any deterministic online algorithm for computing LRS requires \(Ω(n)\) bits of peak working space in the worst case, even over a constant-size alphabet. Through reductions from online LRS computation, we extend this lower bound to deterministic online algorithms maintaining either an arbitrary smallest suffixient set augmented with the length of the supermaximal right extension represented by each selected position, or the position-only smallest suffixient set obtained by selecting the rightmost occurrence of every such extension. For constructing smallest suffixient sets, our algorithms are the first online solutions using compressed working space, improving the $O(n)$-word space required by previous online constructions. For compressed-space online LRS computation, compared with the algorithm of Prezza and Rosone~[CiE 2020], our bounds improve their $O(\log^2 n)$ amortized time per character by factors of $Θ(\log\log n)$ and $Θ((\log\log n)^2)$, respectively, while also providing worst-case guarantees.