Time-Optimal Construction of String Synchronizing Sets

arXiv:2602.11324v1 Announce Type: new
Abstract: 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 $tau$-synchronizing set of a length-$n$ string is a set of $O(n/tau)$ positions, chosen via their length-$2tau$ contexts, such that (outside highly periodic regions) at least one position in every length-$tau$ 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..sigma)^n$ in $O(nlogsigma/log n)$ time so that, for any $tauin[1..n]$, a $tau$-synchronizing set of $T$ can be constructed in $O((nlogtau)/(taulog n))$ time. Both bounds are optimal in the word RAM model with word size $w=Theta(log n)$. Previously, the construction time was $O(n/tau)$, either after an $O(n)$-time preprocessing [Kociumaka, Radoszewski, Rytter, Wale’n; SICOMP 2024], or without preprocessing if $tau<0.2log_sigma n$ [Kempa, Kociumaka; STOC 2019].
A simple version of our method outputs the set as a sorted list in $O(n/tau)$ time, or as a bitmask in $O(n/log n)$ time. Our optimal construction produces a compact fully indexable dictionary, supporting select queries in $O(1)$ time and rank queries in $O(log(tfrac{logtau}{loglog n}))$ time, matching unconditional cell-probe lower bounds for $taule n^{1-Omega(1)}$.
We achieve this via a new framework for processing sparse integer sequences in a custom variable-length encoding. For rank and select queries, we augment the optimal variant of van Emde Boas trees [Pu{a}trac{s}cu, Thorup; STOC 2006] with a deterministic linear-time construction. The above query-time guarantees hold after preprocessing time proportional to the encoding size (in words).