Smallest suffixient set maintenance in near-real-time

The size of the $\mathit{\text{smallest}}\mathit{\text{suffixient}}\mathit{\text{set}}$ of positions of a string recently emerged as a new measure of string $\mathit{\text{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.