4 papers
Online Computation of the Longest Repeating Suffix and Smallest Suffixient Sets via Incremental Run-Length BWT-based Indexes
Paola Bonizzoni, Younan Gao, Dominik Köppl +1
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 on…
Smallest suffixient set maintenance in near-real-time
Dominik Köppl, Gregory Kucherov
The size of the \textit{smallest suffixient set} of positions of a string recently emerged as a new measure of string \textit{repetitiveness} -- a measure reflecting how much of re…
Near-real-time Solutions for Online String Problems
Dominik Köppl, Gregory Kucherov
Based on the Breslauer-Italiano online suffix tree construction algorithm (2013) with double logarithmic worst-case guarantees on the update time per letter, we develop near-real-t…
Online computation of normalized substring complexity
Gregory Kucherov, Yakov Nekrich
The normalized substring complexity of a string is defined as , where is the number of \textit{distinct} substrings of length . This simply define…