Algorithm computes smallest suffixient arrays in sublinear time O((n log σ)/√log n + min(r, r-bar) log^ε n) when alphabet is small and BWT has few runs.
Smallest suffixient set maintenance in near-real-time
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
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 repetitive content the string contains. We study how to maintain the smallest suffixient set online in near-real-time, that is with small (in our case, polyloglog) worst-case time on processing each letter. Two frameworks are considered: when the text is given letter-by-letter in either a right-to-left or left-to-right direction. Our central algorithmic tool is Weiner's suffix tree algorithm and associated algorithmic primitives for its efficient implementation.
fields
cs.DS 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
A linear-time one-pass practical algorithm for building smallest suffixient sets is presented and empirically shown to dominate prior constructions.
citing papers explorer
-
Computing Smallest Suffixient Arrays in Sublinear Time
Algorithm computes smallest suffixient arrays in sublinear time O((n log σ)/√log n + min(r, r-bar) log^ε n) when alphabet is small and BWT has few runs.
-
Practical Linear-Time Computation of Smallest Suffixient Sets
A linear-time one-pass practical algorithm for building smallest suffixient sets is presented and empirically shown to dominate prior constructions.