Time-Optimal Construction of String Synchronizing Sets

A key principle in string processing is local consistency: using short contexts to handle matching fragments of a string consistently. String synchronizing sets [Kempa, Kociumaka; STOC 2019] are an influential instantiation of this principle. A $τ$-synchronizing set of a length-$n$ string is a set of $O(n/τ)$ positions, chosen via their length-$2τ$ contexts, such that (outside highly periodic regions) at least one position in every length-$τ$ window is selected. Among their applications are faster algorithms for data compression, text indexing, and string similarity in the word RAM model. We show how to preprocess any string $T \in [0..σ)^n$ in $O(n\logσ/\log n)$ time so that, for any $τ\in[1..n]$, a $τ$-synchronizing set of $T$ can be constructed in $O((n\logτ)/(τ\log n))$ time. Both bounds are optimal in the word RAM model with word size $w=Θ(\log n)$. Previously, the construction time was $O(n/τ)$, either after an $O(n)$-time preprocessing [Kociumaka, Radoszewski, Rytter, Waleń; SICOMP 2024], or without preprocessing if $τ