Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes

Jul 16, 2026

Upload by Liam

Online computation of the longest repeating suffix (LRS) and construction of smallest suffixient sets are revisited with compressed-space techniques. The work provides the first compressed-space online construction of smallest suffixient sets and introduces two space–time trade-offs for LRS and suffixient sets, parameterized by the number of runs in the run-length Burrows–Wheeler transform of the reverse string. It also proves Ω(n) peak working-space lower bounds for deterministic online LRS, extending them to online maintenance variants.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages25

Reading Time1 h 3 min

Introduction

Related Work

arXiv :2607 .05004v 1 [ cs .DS] 6 Jul 2026 Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes Paola Bonizzoni \# Ñ Department of Computer Science, University of Milano-Bicocca, Italy Younan Gao \# Ñ Department of Computer Science, University of Milano-Bicocca, Italy Dominik Köppl \# Ñ University of Yamanashi, Kofu, Japan Gregory Kucherov \# Ñ LIGM, CNRS and Gustave Eiffel University, Marne-la-Vallée, France ~~ Abstract ~~ We revisit the online construction of smallest suffixient sets and the online computation of the 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(log2 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(log2 n) amortized time per character by factors of Θ(log log n) and Θ((log log n)2 ) , respectively, while also providing worst-case guarantees. 2012 ACM Subject Classification Theory of computation → Data structures design and analysis Keywords and phrases Online algorithms, compressed data structures, run-length Burrows-Wheeler transform, longest repeating suffix, smallest suffixient sets, string repetitiveness Funding Paola Bonizzoni and Younan Gao have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement PANGAIA No. 872539, as well as from grant MIUR 2022YRB97K (PINC, Pangenome Informatics: From Theory to Applications), funded by the European Union under the NextGenerationEU programme, Mission 4 . Dominik Köppl: JSPS KAKENHI Grant Number 25K21150 1 Introduction Computing the longest repeating suffix (LRS) is a classical problem in which for a text T [1..n], the value LRS [i] stores the length of the longest suffix of T [1..i] that occurs at least twice in 2 Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets T [1..i] . This information is useful when solving pattern analysis and data compression [27], especially by analyzing repetitions in the text [14], and has applications in deriving the Lempel-Ziv factorization [17] . Smallest suffixient sets [6] were recently introduced as a measure of string repetitiveness, motivated by the study of highly repetitive data such as genomic collections. The definition of suffixient sets is based on the notion of right-maximal substrings: substrings that occur in the text and can be followed by at least two distinct characters. These substrings correspond to the branching points, or internal nodes, of the suffix tree. Suffixient sets capture this bran

FAQs

What are the longest repeating suffix (LRS) values computing for each prefix?

For each position i, LRS[i] stores the length of the longest suffix of T[1..i] that occurs at least twice. It reflects the longest repeated suffix ending at the newly read character.

How do smallest suffixient sets relate to right-maximal substrings and LRS computation?

Smallest suffixient sets are defined via right-maximal substrings and cover one-character right extensions of those substrings. The previous occurrences of LRS[i] can be witnessed by right extensions represented by the smallest suffixient set for the reverse of the current prefix.

What space–time trade-offs and lower bounds are established in the paper?

Two space–time trade-offs are given for online construction and online LRS computation in compressed working space, depending on run counts r in the run-length BWT. The paper proves that any deterministic online algorithm for LRS needs Ω(n) peak working space in the worst case and extends this lower bound to related suffixient-set maintenance variants.

Jul 16, 2026

Upload by Liam