Time-Optimal Construction of String Synchronizing Sets

Ellert, Jonas; Kociumaka, Tomasz

doi:10.4230/LIPIcs.STACS.2026.36

Time-Optimal Construction
of String Synchronizing Sets

Jonas Ellert

DIENS, École normale supérieure de Paris, PSL Research University, France Tomasz Kociumaka

Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Abstract

A powerful design principle behind many modern string algorithms is local consistency: breaking the symmetry between string positions based on their small contexts so that matching fragments are handled consistently. Among the most influential instantiations of this principle are string synchronizing sets [Kempa & Kociumaka; STOC 2019]. A $\tau$ -synchronizing set of a string of length $n$ is a set of $O(n/\tau)$ string positions, chosen using their length- $2\tau$ contexts, such that (outside of highly periodic regions) every block of $\tau$ consecutive positions contains at least one element of the set. Synchronizing sets have found dozens of applications in diverse settings, from quantum and dynamic algorithms to fully compressed computation. In the classic word RAM model, particularly for strings over small alphabets, they enabled faster solutions to core problems in data compression, text indexing, and string similarity.

In this work, we show that any string $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in $O(n\log\sigma/\log n)$ time so that, for any given integer $\tau\in[1\mathop{.\,.}n]$ , a $\tau$ -synchronizing set of $T$ can be constructed in $O((n\log\tau)/(\tau\log n))$ time. Both bounds are optimal in the word RAM model with machine word size $w=\Theta(\log n)$ , matching the information-theoretic minimum for the input and output sizes, respectively. Previously, constructing a $\tau$ -synchronizing set required $O(n/\tau)$ time after an $O(n)$ -time preprocessing [Kociumaka, Radoszewski, Rytter, and Waleń; SICOMP 2024], or, in the restricted regime of $\tau<0.2\log_{\sigma}n$ , without any preprocessing needed [Kempa & Kociumaka; STOC 2019].

A simple instantiation of our method outputs the synchronizing 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\!\left(\log\!\left(\tfrac{\log\tau}{\log\log n}\right)\right)$ time. The latter complexity matches known unconditional cell-probe lower bounds for $\tau\leq n^{1-\Omega(1)}$ .

To achieve this, we introduce a general framework for efficiently processing sparse integer sequences via a custom variable-length encoding. We also augment the optimal variant of van Emde Boas trees [Pătraşcu & Thorup; STOC 2006] with a deterministic linear-time construction. When the set is represented as a bitmask under our sparse encoding, the same guarantees for select and rank queries hold after preprocessing in time proportional to the size of our encoding (in words).

Keywords and phrases:

synchronizing sets, local consistency, packed strings

Funding:

Jonas Ellert: Partially funded by grant ANR20-CE48-0001 from the French National Research Agency.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pattern matching

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In many string processing tasks, one can afford a relatively costly preprocessing for a small fraction of positions in the input string. The choice of these positions often governs how useful the preprocessing is. The most natural selection mechanisms rely only on the length $n$ of the input string and the “selection rate” $\frac{1}{\tau}$ ; this includes selecting multiples of $\tau$ , sampling positions uniformly at random, as well as difference covers [31]. Although these simple mechanisms are sufficient in some scenarios, the principle of a locally consistent selection has enabled a myriad of new applications. Here, the idea is to select a position $i$ based on the symbols at the nearby positions, without looking at the integer $i$ itself. This ensures that any two positions are handled in the same way whenever they appear in the same context.

The concept of local consistency can be traced back to Sahinalp and Vishkin’s locally consistent parsing [38, 39, 40]. Further hierarchical parsing mechanisms appeared in [11, 12, 19, 20, 32]. Their drawback is that the context size is typically bounded in terms of the number of fixed-level phrases of the parsing, which can vary between regions of the string.

Local consistency is also frequently used in applied research, especially bioinformatics, where minimizers [36, 41] are the most popular mechanism. Here, the context size is easily controlled, but the number of selected positions is known to be ${\mathcal{O}}(n/\tau)$ only for random strings.

String synchronizing sets [22] are a relatively recent local consistency mechanism that addresses the two issues with previous alternatives, paving the way for many more applications (see a dedicated paragraph near the end of this section). A $\tau$ -synchronizing set for a length- $n$ string $T$ is a set $\mathsf{Sync}\subseteq[0\mathop{.\,.}n-2\tau]$ satisfying two conditions: The consistency condition states that, if two positions $i, j$ share their size- ${\mathcal{O}}(\tau)$ contexts (formalized as $T[i\mathop{.\,.}i+2\tau)=T[j\mathop{.\,.}j+2\tau)$ ), then either both positions are synchronizing ( $i,j\in\mathsf{Sync}$ ) or neither of them is ( $i,j\notin\mathsf{Sync}$ ). The density condition requires that, among every $\tau$ consecutive positions in $T$ , at least one belongs to $\mathsf{Sync}$ , except in highly periodic regions of $T$ (see Definition 5.1 for a formal definition). The central contribution of Kempa and Kociumaka [22] is that every length- $n$ string $T$ admits, for every positive integer $\tau<\frac{1}{2}n$ , a $\tau$ -synchronizing set of size ${\mathcal{O}}(n/\tau)$ that can be constructed deterministically in ${\mathcal{O}}(n)$ time. This construction uses sliding window minima, similarly to how minimizers are defined.

The original motivation for string synchronizing sets was to efficiently process strings over small alphabets of size $\sigma=n^{o(1)}$ . In this regime, one can store $\Theta(\log_{\sigma}n)=\omega(1)$ symbols in a single machine word (integer variable) of $\Theta(\log n)$ bits, which allows solving problems in $o(n)$ time, e.g., in ${\mathcal{O}}(n/\log_{\sigma}n)$ time, proportional to the size of the input in machine words. The main algorithms of [22] utilize $\tau$ -synchronizing sets for a small $\tau=\Theta(\log_{\sigma}n)$ , which are built in ${\mathcal{O}}(n/\log_{\sigma}n)$ time. More generally, [22] provides an ${\mathcal{O}}(n/\tau)$ -time $\tau$ -synchronizing set construction for every $\tau<\frac{1}{5}\log_{\sigma}n$ by adapting the ${\mathcal{O}}(n)$ -time construction for arbitrary $\tau$ .

Several further works [2, 8, 28] rely on a hierarchy of $\tau$ -synchronizing sets constructed for different values of $\tau$ . Kociumaka, Radoszewski, Rytter, and Waleń [28] build such a hierarchy using a novel construction algorithm based on restricted recompression, a locally consistent parsing scheme that modifies recompression by Jeż [19, 20]. After an ${\mathcal{O}}(n)$ -time preprocessing, their algorithm constructs a $\tau$ -synchronizing set (given any $\tau$ ) in ${\mathcal{O}}(n/\tau)$ time.

While the two existing constructions have already been very impactful, several natural questions remain open, limiting further use cases. The following is perhaps the simplest one:

Can one construct a small $\tau$ -synchronizing set in $o(n)$ time if $\tau\geq\log_{\sigma}n$ and $\sigma=n^{o(1)}$ ?

In general, we can ask for a single construction algorithm subsuming the two current methods:

Is there an algorithm that, after ${\mathcal{O}}(n/\log_{\sigma}n)$ -time preprocessing of a given string, allows constructing a $\tau$ -synchronizing set in ${\mathcal{O}}(n/\tau)$ time for any given $\tau<\frac{1}{2}n$ ?

The first main result of this work, presented in Sections 3, 4, and 5, answers both questions positively:

Theorem 1.1 (Simplified version of Theorem 5.3).

A string $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given $\tau\leq\frac{1}{2}n$ , a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ of size ${|\mathsf{Sync}|<\frac{70n}{\tau}}$ can be constructed in ${\mathcal{O}}(\frac{n}{\tau})$ time.

Our algorithm returns $\mathsf{Sync}$ as a sorted list, but the same techniques allow returning $\mathsf{Sync}$ as a bitmask in ${\mathcal{O}}(n/\log_{\sigma}n)$ time, which is faster when $\tau=o(\log_{\sigma}n)$ ; see Theorem 5.4.

While these two representations are compact (asymptotically optimal up to a constant factor) for ${\mathcal{O}}(n/\tau)$ -size subsets when $\tau=n^{\Omega(1)}$ and $\tau={\mathcal{O}}(1)$ , respectively, we can hope for a smaller representation and a faster construction algorithm for intermediate values of $\tau$ . We address this in Section 6, where we provide an ${\mathcal{O}}(\frac{n\log\tau}{\tau\log n})$ -time algorithm that outputs a representation supporting efficient select and rank queries (asking for the $r$ -th smallest synchronizing position and the number of synchronizing positions smaller than $i$ , respectively).

Theorem 1.2 (Simplified version of Corollary 6.20).

A string $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given $\tau\leq\frac{1}{2}n$ , a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ of size $|\mathsf{Sync}|<\frac{70n}{\tau}$ can be constructed in ${\mathcal{O}}(\frac{n\log\tau}{\tau\log n})$ time. The set is reported in an ${\mathcal{O}}(\frac{n\log\tau}{\tau})$ -bit representation that supports select queries in ${\mathcal{O}}(1)$ time and rank queries in ${\mathcal{O}}(\log\frac{\log\tau}{\log\log n})$ time.

As discussed in Lemma 6.1, our representation size is asymptotically optimal. Hence, the preprocessing time and the construction time are also optimal for the machine word size of $\Theta(\log n)$ bits. The time complexity of rank queries reduces to constant time for $\tau=\log^{{\mathcal{O}}(1)}n$ and matches the unconditional lower bound of Pătraşcu and Thorup [33] for $\tau\leq n^{1-\Omega(1)}$ .

Our Techniques.

The algorithm behind Theorem 1.1 builds upon the construction of [28]. For this, in Section 3, we show how to implement restricted recompression in ${\mathcal{O}}(n/\log_{\sigma}n)$ time. During the first $K=\Theta(\log\log_{\sigma}n)$ rounds, we simulate restricted recompression on every possible length- ${\mathcal{O}}(\log_{\sigma}n)$ context and keep track of how many times each context occurs in the input string. In the remaining rounds, we process each phrase in constant time. What enables such an approach is that the context size in the $k$ -th round of restricted recompression is bounded by ${\mathcal{O}}(\lambda_{k})$ and the number of phrases is ${\mathcal{O}}(n/\lambda_{k})$ , where $\lambda_{k}=2^{\Theta(k)}$ .

Before we can derive Theorem 1.1 in Section 5, we also need a data structure for reporting runs (maximal periodic fragments) in the input string, which we present in Section 4.

Upon a transition from Theorem 1.1 to Theorem 1.2, several seemingly simple steps become difficult to implement. The prevailing challenge is to process sparse integer sequences in $o(1)$ time per non-zero entry. Our strategy is to introduce a variable-length encoding of such sequences, implement operations on them using transducers (finite automata with output tapes), and provide a general method for speeding up transducer execution using precomputed tables. We believe that our approach, outlined in Section 6, will be useful in many other contexts to efficiently manipulate compact data representations.

In particular, in order to provide rank and select support in Theorem 1.2, we provide a new compact variant of van Emde Boas trees [42] matching the optimal query time bounds of Pătraşcu and Thorup [33] and, unlike existing variants, constructible deterministically in linear time.

Theorem 1.3.

Let $S\subseteq[0\mathop{.\,.}2^{\ell})$ of size $\lvert S\rvert=n$ with $\ell\geq 2$ and $n,2^{\ell}\in 2^{{\mathcal{O}}(w)}$ be given as an array of $\ell$ -bit integers in increasing order. For $m\geq n$ , let $a=\lg(m/n)+\lg w$ . A deterministic data structure that answers rank and predecessor queries in ${\mathcal{O}}(\lg\frac{\ell-\lg m}{a})$ time can be built in ${\mathcal{O}}(m)$ time and words of space.

If the input set is provided using our sparse representation, we even achieve construction time proportional to the number of machine words in the compact encoding of the set (and, in many cases, sublinear in the number of set elements); see Section 6.3.

Applications of Synchronizing Sets.

Since their introduction in 2019, string synchronizing sets have found numerous applications across a variety of settings. For strings over small alphabets, they enabled $o(n)$ -time algorithms for fundamental decades-old tasks such as Burrows–Wheeler transform [22], Lempel–Ziv factorization [15, 26], and the longest common factor problem [8]. They are also behind the only $o(n)$ -time constructions of compact suffix array and suffix tree representations [25] and data structures for longest common extension (LCE) [22, 13] and internal pattern matching (IPM) [28] queries. Further applications include detecting regularities in strings, such as palindromes [10], squares [9], and covers [35].

In some applications, including IPM queries [28] and the longest common factor with mismatches problem [8], string synchronizing sets also enabled speed-ups for large alphabets. In certain cases, such as for the longest common circular factor problem [2], the obtained speed-up is as large as from ${\mathcal{O}}(n^{2})$ to ${\mathcal{O}}(n\log^{{\mathcal{O}}(1)}n)$ . Polynomial-factor speed-ups also arise beyond the classic setting, thanks to adaptations of synchronizing sets (with custom constructions) to the dynamic [23], quantum [1, 21], and fully-compressed [24, 26] settings.

Other Local Consistency Mechanisms.

There are dozens of local consistency mechanisms with different features and use cases. Beyond those mentioned above, theoretical methods include sample assignments [27] and the partitioning sets [6], which predate synchronizing sets. In the algorithm engineering community, beyond minimizers (see [17, Chapter 6] for a very recent literature overview), notable alternatives include locally consistent anchors [30, 3] and the prefix-free parsing [7], which is particularly useful in the context of suffix sorting.

2 Preliminaries

For $i,j\in\mathbb{Z}$ , we write $[i\mathop{.\,.}j]=[i\mathop{.\,.}j+1)=(i-1\mathop{.\,.}j]=(i-1\mathop{.\,.}j+1)$ to denote $\{h\in\mathbb{Z}\mid i\leq h\leq j\}$ . We also write $\lg i$ to denote $\log_{2}\max(1,i)$ . A string $T$ of length $\lvert T\rvert=n$ over alphabet $[0\mathop{.\,.}\sigma)$ is a sequence of $n$ symbols from $[0\mathop{.\,.}\sigma)$ . For $i,j\in[0\mathop{.\,.}n)$ , the $i$ -th symbol is $T[i]$ , and the sequence $T[i]T[i+1]\cdots T[j]$ is denoted by $T[i\mathop{.\,.}j]=T[i\mathop{.\,.}j+1)$ (which is the empty string if $i>j$ ). For $i^{\prime},j^{\prime}\in[0\mathop{.\,.}n)$ , consider $T[i^{\prime}\mathop{.\,.}j^{\prime}]$ . We may interpret $T[i\mathop{.\,.}j]$ and $T[i^{\prime}\mathop{.\,.}j^{\prime}]$ as substrings. We then write $T[i\mathop{.\,.}j]\cong T[i^{\prime}\mathop{.\,.}j^{\prime}]$ and say that the substrings match if and only if $j-i=j^{\prime}-i^{\prime}$ and $\forall_{h\in[0\mathop{.\,.}j-i]}\;T[i+h]=T[i^{\prime}+h]$ . We can choose to interpret them as fragments instead, in which case we write $T[i\mathop{.\,.}j]=T[i^{\prime}\mathop{.\,.}j^{\prime}]$ and say that the fragments are equal if and only if $i=i^{\prime}$ and $j=j^{\prime}$ (or if both fragments are empty). For fragments $T[i\mathop{.\,.}j]$ and $T[i^{\prime}\mathop{.\,.}j^{\prime}]$ , we denote their intersection as $T[i\mathop{.\,.}j]\cap T[i^{\prime}\mathop{.\,.}j^{\prime}]=T[\max(i,i^{\prime% })\mathop{.\,.}\min(j,j^{\prime})]$ .

The concatenation of two strings $T[0\mathop{.\,.}n)$ and $S[0\mathop{.\,.}m)$ is defined as $T\cdot S:=T[0]\cdots T[n-1]\allowbreak S[0]\cdots S[m-1]$ , and the $k$ -times concatenation of $T$ with itself is written as $T^{k}$ , where $k\in\mathbb{Z}_{\geq 0}$ . Note that $T^{0}$ is the empty string. The unique primitive root $R$ of a non-empty string $T$ is the shortest prefix of $T$ such that there is $k\in\mathbb{Z}_{+}$ with $T=R^{k}$ .

Model of Computation.

We assume the word RAM model (see, e.g., [18]) with words of $w=\Theta(\lg n)$ bits when processing a text $T\in[0\mathop{.\,.}\sigma)^{n}$ with $\sigma\in n^{{\mathcal{O}}(1)}$ . The text and all other strings encountered throughout the paper are assumed to be in $\lceil\lg\sigma\rceil$ -bit representation, i.e., each symbol uses exactly $\lceil\lg\sigma\rceil$ bits, the entire text occupies $\Theta(n\lg\sigma)$ consecutive bits of memory, and each memory word fits $\Theta(\log_{\sigma}n)$ symbols. Using arithmetic and bitwise operations, we can extract any substring of length up to $\lfloor\log_{\sigma}n\rfloor$ in a single word in ${\mathcal{O}}(1)$ time.

In the analysis, $\sigma$ will only appear when the claimed (pre-)processing time is ${\mathcal{O}}(n/\log_{\sigma}n)$ . For obtaining these results, we assume that $\lg\sigma\in\mathbb{Z}$ , that the symbol $\texttt{\textdollar}:=\sigma-1$ does not occur in $T[0\mathop{.\,.}n)$ , and that we have access to the ${\lg\sigma}$ -bit representation of $T[-n\mathop{.\,.}2n):=\texttt{\textdollar}^{n}\cdot T[0\mathop{.\,.}n)\cdot% \texttt{\textdollar}^{n}$ . This assumption is without loss of generality, which we show in the complete version.

Accessing lookup tables with substrings.

We will use substrings of length at most $(\log_{\sigma}n)/4$ to access lookup tables. For a string $S\in[0\mathop{.\,.}\sigma)^{*}$ of length $0\leq\lvert S\rvert\leq(\log_{\sigma}n)/4$ , we define its integer representation ${\textnormal{{{int}}}}(S)$ as follows:

$\blacksquare$

${\textnormal{{{int}}}}(S)$ consists of $2\cdot\lfloor(\lg n)/4\rfloor$ bits, i.e., ${\textnormal{{{int}}}}(S)\in[0\mathop{.\,.}2^{2\cdot\lfloor(\lg n)/4\rfloor})% \subseteq[0\mathop{.\,.}\lfloor\sqrt{n}\rfloor)$ .
$\blacksquare$

The upper half of ${\textnormal{{{int}}}}(S)$ contains the binary representation of $S$ (consisting of $\lvert S\rvert\cdot\lg\sigma\leq\lfloor(\lg n)/4\rfloor$ bits), padded with 0-bits.
$\blacksquare$

The lower half of ${\textnormal{{{int}}}}(S)$ stores the length $\lvert S\rvert$ . This value can indeed be stored in $\lceil\lg(1+(\log_{\sigma}n)/4)\rceil<\lfloor(\lg n)/4\rfloor$ bits. (The inequality holds if $n$ exceeds some constant.)

As mentioned earlier, extracting a substring $S=T[i\mathop{.\,.}j)$ of length $0\leq j-i\leq(\log_{\sigma}n)/4$ takes constant time. Mapping $S$ to ${\textnormal{{{int}}}}(S)$ and vice versa also takes constant time.

2.1 Revisiting Restricted Recompression

Following [28], we define integer sequences $(\lambda_{k})_{k=0}^{\infty}$ so that $\lambda_{k}={\left(\frac{8}{7}\right)}^{\lfloor k/2\rfloor}$ and $(\alpha_{k})_{k=0}^{\infty}$ so that $\alpha_{0}=1$ and recursively $\alpha_{k}=\alpha_{k-1}+\lfloor\lambda_{k-1}\rfloor$ . These sequences control, respectively, the phrase lengths and context sizes at each recompression round. As observed in [28], $\alpha_{k+1}\leq 16\lambda_{k}$ holds for every $k\in\mathbb{Z}_{\geq 0}$ . Our goal is to compute the following sets:

Proposition 2.1 ([28, Propositions 3.4 and 4.7]).

For every length- $n$ text $T$ , there exists a descending chain $[1\mathop{.\,.}n)=\textnormal{{B}}_{0}\supseteq\textnormal{{B}}_{1}\supseteq% \cdots\supseteq\textnormal{{B}}_{q}=\emptyset$ with $q={\mathcal{O}}(\lg n)$ such that, for each $k\in\mathbb{Z}_{\geq 0}$ , the set $\textnormal{{B}}_{k}$ satisfies the following:

(a)

$\lvert\textnormal{{B}}_{k}\rvert\leq\frac{4n}{\lambda_{k}}$
(b)

For $i,j\in[\alpha_{k}\mathop{.\,.}n-\alpha_{k}]$ , if $i\in\textnormal{{B}}_{k}$ and ${T[i-\alpha_{k}\mathop{.\,.}i+\alpha_{k})}\cong{T[j-\alpha_{k}\mathop{.\,.}j+% \alpha_{k})}$ , then $j\in\textnormal{{B}}_{k}$ .
(c)

If $i, j$ are consecutive positions in $\textnormal{{B}}_{k}\cup\{0,n\}$ , then $T[i\mathop{.\,.}j)$ has length at most $\frac{7}{4}\lambda_{k}$ , or its primitive root has length at most $\lambda_{k}$ .

If $T\in[0\mathop{.\,.}n^{{\mathcal{O}}(1)})^{n}$ , then one can construct $\textnormal{{B}}_{0}\supseteq\cdots\supseteq\textnormal{{B}}_{q-1}\supsetneq% \textnormal{{B}}_{q}=\emptyset$ in ${\mathcal{O}}(n)$ time.

$\blacktriangleright$ Remark 2.2.

While $q={\mathcal{O}}(\lg n)$ is not stated in [28, Propositions 3.4 and 4.7], it readily follows from Proposition 2.1(a), in which we have $\textnormal{{B}}_{k}=\emptyset$ if $\lambda_{k}>4n$ (see also [28, p. 1542]).

Our sublinear-time solution for the initial rounds of restricted recompression closely follows the structure of the linear-time algorithm in the proof of Proposition 2.1 (see [28, Proposition 4.7]). We now give a conceptual description of this algorithm (ignoring implementation details). If we can show that the new solution is functionally identical to this algorithm, then it correctly computes the sets satisfying Proposition 2.1.

We start with the set $\textnormal{{B}}_{0}=[1\mathop{.\,.}n)$ . Assume that, for some $k\in[0\mathop{.\,.}q)$ , we have computed the set $\textnormal{{B}}_{k}=\{f_{1},\dots,f_{m}\}$ with $f_{1}<f_{2}<\dots<f_{m}$ . Let $f_{0}=0$ and $f_{m+1}=n$ , and define $F_{i}=T[f_{i}\mathop{.\,.}f_{i+1})$ for $i\in[0\mathop{.\,.}m]$ . Now we compute the set $\textnormal{{B}}_{k+1}$ .

Case 1: $𝒌$ is even.

For each $i\in[1\mathop{.\,.}m]$ , we add $f_{i}$ to $\textnormal{{B}}_{k+1}$ if and only if $\max(\lvert F_{i-1}\rvert,\lvert F_{i}\rvert)>\lambda_{k}$ or $F_{i-1}\ncong F_{i}$ (or both). This can be viewed as merging each run of identical phrases (of length at most $\lambda_{k}$ ) into a single new phrase (see Figure 1(a)).

(a) Construction of

\textnormal{{B}}_{k+1}

for even

k

. Equal labels indicate matching substrings. In this example, F is the only phrase of length more than

\lambda_{k}

before constructing

\textnormal{{B}}_{k+1}

.

(b) Construction of

\textnormal{{B}}_{k+1}

for odd

k

. Equal labels indicate matching substrings. In this example, F is the only phrase of length more than

\lambda_{k}

before constructing

\textnormal{{B}}_{k+1}

. White, gray, and green blocks respectively correspond to phrases in

L

, phrases in

R

, and merged phrase pairs.

(c) Multigraph (left) and weighted graph (right) for the factorization from Figure 1(b), where

\lvert E\rvert=11

and the sum of weights from

L

to

R

is

5

.

Figure 1: Even and odd rounds of restricted recompression.

Case 2: $𝒌$ is odd.

Let $\mathcal{F}=\{F_{i}\mid i\in[0\mathop{.\,.}m]\textnormal{\ and\ }\lvert F_{i}% \rvert\leq\lambda_{k}\}$ be the set of distinct phrases of length at most $\lambda_{k}$ , viewed as strings rather than fragments (so matching phrases represent the same element of $\mathcal{F}$ ). We partition $\mathcal{F}$ into sets $L$ and $R$ . For each $i\in[1\mathop{.\,.}m]$ , we add $f_{i}$ to $\textnormal{{B}}_{k+1}$ unless both $F_{i-1}\in L$ and $F_{i}\in R$ . This amounts to merging adjacent pairs of phrases whenever the left phrase is in $L$ and the right phrase is in $R$ (see Figure 1(b)).

The sets $L, R$ are computed by modeling the factorization as a directed multigraph whose nodes are the elements of $\mathcal{F}$ . For every $i\in[1\mathop{.\,.}m]$ , we add an edge from $F_{i-1}$ to $F_{i}$ if $\max(\lvert F_{i-1}\rvert,\lvert F_{i}\rvert)\leq\lambda_{k}$ . (Due to the preceding even round, it is clear that $F_{i-1}\ncong F_{i}$ .) Let $E$ be the multiset of all edges. To obtain the properties in Proposition 2.1, it suffices to partition $\mathcal{F}$ into $L$ and $R$ so that at least $\frac{1}{4}\cdot\lvert E\rvert$ edges go from $L$ to $R$ . This can be achieved by approximating a maximum directed cut in the multigraph (e.g., using [28, Lemma A.1]).

Equivalently, we can use a weighted directed graph instead of a multigraph. The set of nodes is still $\mathcal{F}$ . For each pair of nodes $F^{\prime},F^{\prime\prime}$ , the weight of the edge from $F^{\prime}$ to $F^{\prime\prime}$ is the number of edges from $F^{\prime}$ to $F^{\prime\prime}$ in the multigraph. Then, we partition $\mathcal{F}$ into $L$ and $R$ so that the sum of the weights of edges from $L$ to $R$ is at least $\frac{1}{4}\cdot\lvert E\rvert$ (see Figure 1(c)).

3 Restricted Recompression in Sublinear Time

In this section, we show how to implement restricted recompression in ${\mathcal{O}}(n/\log_{\sigma}n)$ time. If $\log_{\sigma}n$ is constant, then we can afford linear time and use the solution from [28]. Hence, assume $\log_{\sigma}n\geq 256$ . We fix $K:=2\cdot\lfloor\log_{8/7}\left(256^{-1}\cdot{\log_{\sigma}n}\right)\rfloor$ . Recalling that $\lambda_{K}=(\frac{8}{7})^{\lfloor K/2\rfloor}$ , we observe that ${\frac{7}{8}\cdot 256^{-1}\cdot\log_{\sigma}n}\leq\lambda_{K}\leq 256^{-1}% \cdot\log_{\sigma}n$ . During rounds $0,\dots,K$ of restricted recompression, by Proposition 2.1(b), the phrase boundaries are chosen based on short contexts of length at most $2\alpha_{K}\leq 32\lambda_{K}\leq 8^{-1}\cdot\log_{\sigma}n$ , and hence this process can be accelerated using word-packing techniques. After round $K$ , the number of boundary positions is at most $\frac{4n}{\lambda_{K}}={\mathcal{O}}(n/\log_{\sigma}n)$ by Proposition 2.1(a), and we can implement the remaining rounds in ${\mathcal{O}}(n/\log_{\sigma}n)$ time using the linear-time solution presented in [28]. We only need the following straightforward corollaries.

Definition 3.1.

Let $\textnormal{{B}}_{k}=\{f_{1},\dots,f_{m}\}\subseteq[1\mathop{.\,.}n)$ with $f_{1}<f_{2}<\dots<f_{m}$ be one of the sets computed in Proposition 2.1, and let $f_{0}=0$ and $f_{m+1}=n$ . We define

$\blacksquare$

the (not necessarily unique) string of phrase names $I_{k}[0\mathop{.\,.}m]$ over alphabet $[0\mathop{.\,.}m]$ , where, for every $i,j\in[0\mathop{.\,.}m]$ , it holds $I_{k}[i]=I_{k}[j]$ if and only if $T[f_{i}\mathop{.\,.}f_{i+1})\cong T[f_{j}\mathop{.\,.}f_{j+1})$ ,
$\blacksquare$

the array ${\textnormal{{{len}}}}_{k}[0\mathop{.\,.}m]$ of phrase lengths with ${\textnormal{{{len}}}}_{k}[i]=f_{i+1}-f_{i}$ for all $i\in[0\mathop{.\,.}m]$ .

Corollary 3.2 (of [28, Proposition 4.7]).

Let $k\in[0\mathop{.\,.}q)$ . Given $\textnormal{{B}}_{k}$ , $I_{k}$ , and ${\textnormal{{{len}}}}_{k}$ , one can compute $\textnormal{{B}}_{k+1}\supseteq\textnormal{{B}}_{k+2}\supseteq\dots\supseteq% \textnormal{{B}}_{q-1}\supsetneq\textnormal{{B}}_{q}=\emptyset$ in ${\mathcal{O}}(n/\lambda_{k})$ time.

Proof.

The algorithm from the proof of [28, Proposition 4.7] uses $\textnormal{{B}}_{k},I_{k}$ , and ${\textnormal{{{len}}}}_{k}$ to compute $\textnormal{{B}}_{k+1},I_{k+1}$ , and ${\textnormal{{{len}}}}_{k+1}$ in ${\mathcal{O}}(\lvert\textnormal{{B}}_{k}\rvert)$ time. Hence, the remaining sets $\textnormal{{B}}_{k+1}\supseteq\textnormal{{B}}_{k+2}\supseteq\dots\supseteq% \textnormal{{B}}_{q}=\emptyset$ can be computed in ${\mathcal{O}}(\sum_{k^{\prime}=k}^{q-1}\lvert\textnormal{{B}}_{k^{\prime}}\rvert)$ time. By Proposition 2.1(a) and the definition of $\lambda_{k^{\prime}}$ , the sum is bounded by ${\mathcal{O}}(n/\lambda_{k})$ . $\hfill\blacktriangleleft$

Corollary 3.3.

Given the elements of $\textnormal{{B}}_{K}$ in increasing order, one can compute the sets $\textnormal{{B}}_{K+1}\supseteq\textnormal{{B}}_{K+2}\supseteq\dots\supseteq% \textnormal{{B}}_{q-1}\supsetneq\textnormal{{B}}_{q}=\emptyset$ in ${\mathcal{O}}(n/\log_{\sigma}n)$ time.

Proof.

Let $\textnormal{{B}}_{K}=\{f_{1},\dots,f_{m}\}$ with $f_{i}<f_{i+1}$ for all $i\in[1\mathop{.\,.}m)$ , and define $f_{0}=0$ and $f_{m+1}=n$ . Note that $m={\mathcal{O}}(n/\lambda_{K})={\mathcal{O}}(n/\log_{\sigma}n)$ by Proposition 2.1(a) and the definitions of $K$ and $\lambda_{K}$ . By Corollary 3.2, it suffices to compute $I_{K}$ and ${\textnormal{{{len}}}}_{K}$ in ${\mathcal{O}}(n/\lambda_{K})$ time, which is trivial for ${\textnormal{{{len}}}}_{K}$ . To compute $I_{K}$ , we first produce a string $I^{\prime}_{K}$ over a slightly larger alphabet. For each $i\in[0\mathop{.\,.}m]$ , we encode phrase $T[f_{i}\mathop{.\,.}f_{i+1})$ as $I^{\prime}_{K}[i]=({\textnormal{{{int}}}}(S_{i}),{\textnormal{{{len}}}}_{K}[i])$ , where $S_{i}$ is the truncated phrase ${T[f_{i}\mathop{.\,.}\min(f_{i+1},f_{i}+2\lambda_{K}))}$ . Trivially, two phrases are identical if and only if they have the same length and primitive root. By Proposition 2.1(c), the primitive root of any phrase is of length at most $\frac{7}{4}\lambda_{K}$ . Since $S_{i}$ is either the entire phrase or a length- $2\lambda_{K}$ prefix of the phrase, it is also a (possibly fractional) power of the primitive root of the phrase. Hence, it is easy to see that we indeed encode two phrases identically if and only if they are identical. Clearly, $I^{\prime}_{K}$ can be computed in ${\mathcal{O}}(m)$ time. We obtain $I_{K}$ by reducing the alphabet to $[0\mathop{.\,.}m]$ using radix sort in ${\mathcal{O}}(n/\log_{\sigma}n)$ time. $\hfill\blacktriangleleft$

3.1 Performing the Initial $𝑲$ Rounds

In the initial rounds of recompression, the weights in the graph of adjacent phrases depend on the abundance of short substrings. Hence, we use the following simple index for counting short substrings. A proof is provided in the full version.

Lemma 3.4.

For any string $T\in[0\mathop{.\,.}\sigma)^{n}$ , in ${\mathcal{O}}(n/\log_{\sigma}n)$ time, we can construct a data structure that answers the following type of query in constant time. Given a string $S\in[0\mathop{.\,.}\sigma)^{*}$ of length at most $(\log_{\sigma}n)/8$ , return the number of occurrences of $S$ in $T$ .

Defining phrase boundaries via substrings.

Instead of directly computing $\textnormal{{B}}_{k}$ , we compute the intermediate representation¹¹1Recall that $T$ is padded so that $T[-n\mathop{.\,.}2n)=\texttt{\textdollar}^{n}\cdot T[0\mathop{.\,.}n)\cdot% \texttt{\textdollar}^{n}$ . Hence, $T[i-\alpha_{k}\mathop{.\,.}i+\alpha_{k})$ with $i\in[0\mathop{.\,.}n]$ is always defined. Also, if ${i\in[0\mathop{.\,.}n]\setminus[\alpha_{k}\mathop{.\,.}n-\alpha_{k}]}$ , then $T[i-\alpha_{k}\mathop{.\,.}i+\alpha_{k})$ is unique in $T[-\alpha_{k}\mathop{.\,.}n+\alpha_{k})$ . $\textnormal{{C}}_{k}=\{T[i-\alpha_{k}\mathop{.\,.}i+\alpha_{k})\mid i\in% \textnormal{{B}}_{k}\cup\{0,n\}\},$ i.e., rather than explicitly listing the boundary positions, we instead list the set of distinct contexts that cause a boundary. From now on, for $k\in[0\mathop{.\,.}q]$ and $i\in\textnormal{{B}}_{k}$ , we say that a string $T[i-\alpha_{k}\mathop{.\,.}i+\alpha_{k})\in\textnormal{{C}}_{k}$ is a boundary context of $\textnormal{{B}}_{k}$ . For every $i\in[0\mathop{.\,.}n]$ , it follows from Proposition 2.1(b) that $i\in\textnormal{{B}}_{k}\cup\{0,n\}$ if and only if $T[i-\alpha_{k}\mathop{.\,.}i+\alpha_{k})\in\textnormal{{C}}_{k}$ .

Lemma 3.5.

The sets $\textnormal{{C}}_{1},\dots,\textnormal{{C}}_{K-1},\textnormal{{C}}_{K}$ can be computed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time, with each set $\textnormal{{C}}_{k}$ encoded as a bitmask of length $\lfloor\sqrt{n}\rfloor$ whose set bits are $\{{\textnormal{{{int}}}}(S):S\in\textnormal{{C}}_{k}\}$ .

Proof.

The sets $\textnormal{{C}}_{1},\dots,\textnormal{{C}}_{K-1},\textnormal{{C}}_{K}$ consist of strings of length up to $2\alpha_{K}\leq 8^{-1}\cdot\log_{\sigma}n$ . We can encode any $S\in\textnormal{{C}}_{k}$ as ${\textnormal{{{int}}}}(S)\in[0\mathop{.\,.}\lfloor\sqrt{n}\rfloor)$ . We construct the data structure from Lemma 3.4 for the padded string $\texttt{\textdollar}^{2\alpha_{K}}\cdot T\cdot\texttt{\textdollar}^{2\alpha_{K}}$ , which allows querying for $S$ . We can also query for strings of the form $\texttt{\textdollar}^{j_{1}}\cdot T[0\mathop{.\,.}j_{2})$ and $T[n-j_{1}\mathop{.\,.}n)\cdot\texttt{\textdollar}^{j_{2}}$ with $j_{1}+j_{2}\leq 2\alpha_{K}$ .

Initialization.

We initialize each of $\textnormal{{C}}_{1},\dots,\textnormal{{C}}_{K}$ as an all-zero bitmask of length $\lfloor\sqrt{n}\rfloor$ . Recall that $\alpha_{0}=1$ . For computing $\textnormal{{C}}_{0}$ , we enumerate all possible length-two strings over $[0\mathop{.\,.}\sigma)$ , except for $\texttt{\textdollar}^{2}$ . For each such string $S$ , we query the data structure from Lemma 3.4. If $S$ occurs in $T$ , we set the ${\textnormal{{{int}}}}(S)$ -th bit of $\textnormal{{C}}_{0}$ to one. Recall that $2\leq 2\alpha_{K}\leq 8^{-1}\cdot\log_{\sigma}n$ ; hence, we can indeed afford to enumerate all strings of length up to $2\alpha_{K}$ (e.g., the $\sigma^{2}$ strings of length two during initialization) in ${\mathcal{O}}(2^{2\alpha_{K}})\subset{\mathcal{O}}(\sqrt{n})$ time.

Preparing round $k+1$ .

Assume that we have already computed $\textnormal{{C}}_{k}$ for some $k\in[0\mathop{.\,.}K)$ , and our goal is to compute $\textnormal{{C}}_{k+1}$ . The main computational challenge is the following. For each length- $2\alpha_{k+1}$ string $S$ over alphabet $[0\mathop{.\,.}\sigma)$ , except for $\texttt{\textdollar}^{2\alpha_{k+1}}$ , we have to decide if $S\in\textnormal{{C}}_{k+1}$ . We enumerate all the ${\mathcal{O}}(\sqrt{n})$ possible strings of length $2\alpha_{k+1}$ . For each such string $S$ , we first check if it is indeed a substring of the padded string $T$ using the data structure from Lemma 3.4. If $S$ is not a substring, then it is not a boundary context of $\textnormal{{B}}_{k+1}$ and can be skipped. Otherwise, we consider its central part $S^{\prime}=S[\alpha_{k+1}-\alpha_{k}\mathop{.\,.}\alpha_{k+1}+\alpha_{k})$ . If $S^{\prime}$ is not a boundary context of $\textnormal{{B}}_{k}$ , i.e., if $S^{\prime}\notin\textnormal{{C}}_{k}$ (a check performed in constant time), then $S$ cannot be a boundary context of $\textnormal{{B}}_{k+1}$ due to $\textnormal{{B}}_{k+1}\subseteq\textnormal{{B}}_{k}$ . Hence, if $S^{\prime}\notin\textnormal{{C}}_{k}$ , we do not have to process $S$ any further.

If, however, it holds $S^{\prime}\in\textnormal{{C}}_{k}$ , then we have to decide whether we will make $S$ a boundary context of $\textnormal{{B}}_{k+1}$ by adding $S$ to $\textnormal{{C}}_{k+1}$ . For the sake of explanation, consider any position $i\in[1\mathop{.\,.}n)$ such that $T[i-\alpha_{k+1}\mathop{.\,.}i+\alpha_{k+1})\cong S$ . We now explain how to compute the minimal values $\ell,r\in[1\mathop{.\,.}\lfloor\lambda_{k}\rfloor]$ such that $i-\ell\in\textnormal{{B}}_{k}\cup\{0,n\}$ and $i+r\in\textnormal{{B}}_{k}\cup\{0,n\}$ . If both values exist, then the factorization induced by $\textnormal{{B}}_{k}$ contains fragments $T[i-\ell\mathop{.\,.}i)$ and $T[i\mathop{.\,.}i+r)$ as phrases. If, however, $\ell$ or $r$ does not exist, then we know that the phrase ending at position $i-1$ or the phrase starting at position $i$ is of length more than $\lfloor\lambda_{k}\rfloor$ (possibly both). When creating $\textnormal{{B}}_{k+1}$ , the algorithm from [28, Proposition 4.7(a)] (see also Section 2.1) merges two adjacent phrases only if both of them are of length at most $\lambda_{k}$ . Hence, if $\ell$ or $r$ does not exist, then the phrases around boundary $i$ cannot be merged, and $i$ is a boundary position in $\textnormal{{B}}_{k+1}$ .

We now explain how to compute $\ell$ or show that it does not exist; the computation for $r$ is symmetric. Consider any $\ell\in[1\mathop{.\,.}\lfloor\lambda_{k}\rfloor]$ . Due to $\alpha_{k+1}=\alpha_{k}+\lfloor\lambda_{k}\rfloor$ and $S\cong T[i-\alpha_{k+1}\mathop{.\,.}i+\alpha_{k+1})$ , it holds

T[i-\alpha_{k}-\ell\mathop{.\,.}i+\alpha_{k}-\ell)\cong S[\lfloor\lambda_{k}% \rfloor-\ell\mathop{.\,.}\lfloor\lambda_{k}\rfloor+2\alpha_{k}-\ell).

Hence, we can check if $i-\ell$ is in $\textnormal{{B}}_{k}\cup\{0,n\}$ by probing $\textnormal{{C}}_{k}$ with $S[\lfloor\lambda_{k}\rfloor-\ell\mathop{.\,.}\lfloor\lambda_{k}\rfloor+2\alpha% _{k}-\ell)$ in constant time. By trying all possible values, finding the minimal suitable $\ell$ takes ${\mathcal{O}}(\lambda_{k})$ time. If both $\ell$ and $r$ exist, then we add a tuple $\langle S,\ell,r\rangle$ to a list $\mathcal{L}$ . Otherwise, as explained above, we have to make $S$ a boundary context of $\textnormal{{B}}_{k+1}$ by adding $S$ to $\textnormal{{C}}_{k+1}$ .

After processing all possible strings $S$ , we have the following situation. If a boundary position in $\textnormal{{B}}_{k}\cup\{0,n\}$ is adjacent to a phrase of length over $\lfloor\lambda_{k}\rfloor$ , then the corresponding boundary context has been added to $\textnormal{{C}}_{k+1}$ . (This is always the case for the contexts $\texttt{\textdollar}^{\alpha_{k+1}}\cdot T[0\mathop{.\,.}\alpha_{k+1})$ and $T[n-\alpha_{k+1}\mathop{.\,.}n)\cdot\texttt{\textdollar}^{\alpha_{k+1}}$ of positions $0$ and $n$ , respectively). If a boundary position in $\textnormal{{B}}_{k}$ has context $S$ and is adjacent to phrases of respective lengths $\ell,r\leq\lfloor\lambda_{k}\rfloor$ , then $\langle S,\ell,r\rangle$ has been added to $\mathcal{L}$ . Since each context has been added to $\mathcal{L}$ at most once, the elements of $\mathcal{L}$ are distinct.

Performing an even round.

Consider a boundary position in $\textnormal{{B}}_{k}$ for which the two adjacent phrases are identical and of length at most $\lfloor\lambda_{k}\rfloor$ . The run of identical phrases will be merged in $\textnormal{{B}}_{k+1}$ , and the boundary position will no longer exist. Hence, we proceed as follows. We consider each element $\langle S,\ell,r\rangle$ of the list $\mathcal{L}$ . If $S[\alpha_{k+1}-\ell\mathop{.\,.}\alpha_{k+1})\ncong S[\alpha_{k+1}\mathop{.\,.% }\alpha_{k+1}+r)$ , then we add $S$ to $\textnormal{{C}}_{k+1}$ ; otherwise, we do nothing (skip the element of $\mathcal{L}$ ).

Performing an odd round.

We have to produce the weighted directed graph described in Section 2.1. The set of nodes is $\mathcal{F}=\bigcup_{\langle S,\ell,r\rangle\in\mathcal{L}}\{S[\alpha_{k+1}-% \ell\mathop{.\,.}\alpha_{k+1}),S[\alpha_{k+1}\mathop{.\,.}\alpha_{k+1}+r)\}.$

For each $\langle S,\ell,r\rangle\in\mathcal{L}$ , we obtain the number $s$ of occurrences of $S$ in the padded $T$ using the data structure from Lemma 3.4. We increase the weight of the edge from $S[\alpha_{k+1}-\ell\mathop{.\,.}\alpha_{k+1})$ to $S[\alpha_{k+1}\mathop{.\,.}\alpha_{k+1}+r)$ by $s$ . (This results in no self-loops, as phrases in $\mathcal{F}$ are of length $\leq\lfloor\lambda_{k}\rfloor$ , and runs of phrases of length $\leq\lfloor\lambda_{k}\rfloor$ have been eliminated in the preceding even round.) Observe that $\lvert\mathcal{L}\rvert={\mathcal{O}}(\sqrt{n})$ , and each element of $\mathcal{L}$ contributes weight to one edge. Therefore, the number of edges is ${\mathcal{O}}(\sqrt{n})$ , and we can approximate the maximum cut in ${\mathcal{O}}(\sqrt{n})$ time (see, e.g., [28, Lemma A.1], which immediately works for weighted graphs). This reveals the two parts $L$ and $R$ used for computing $\textnormal{{B}}_{k+1}$ . We once more consider each $\langle S,\ell,r\rangle\in\mathcal{L}$ and check if $S[\alpha_{k+1}-\ell\mathop{.\,.}\alpha_{k+1})\in L$ and $S[\alpha_{k+1}\mathop{.\,.}\alpha_{k+1}+r)\in R$ . Whenever this is the case, we do nothing (skip the element of $\mathcal{L}$ ). Otherwise, we add $S$ to $\textnormal{{C}}_{k+1}$ .

Time complexity and correctness.

In each round, we have to consider all the ${\mathcal{O}}(\sqrt{n})$ possible strings of length $2\alpha_{k+1}$ . We process each string in ${\mathcal{O}}(\lambda_{k})\subseteq{\mathcal{O}}(\lg n)$ time, dominated by the time needed to compute $\ell$ and $r$ . We spend additional ${\mathcal{O}}(\sqrt{n})$ time to approximate the maximum cut. Recalling that $K={\mathcal{O}}(\log\log n)$ , the overall time is ${\mathcal{O}}(K\cdot\sqrt{n}\cdot\lg n)\subset o(n/\lg n)$ , plus ${\mathcal{O}}(n/\log_{\sigma}n)$ time for the preprocessing of Lemma 3.4. The correctness follows from the fact that the algorithm directly implements the steps described in Section 2.1. $\hfill\blacktriangleleft$

3.2 Reporting the Phrase Boundaries

The number of boundaries in the initial $K$ rounds may significantly exceed ${\mathcal{O}}(n/\log_{\sigma}n)$ , and thus we cannot afford to report them explicitly. Instead, we report a bitmask of length $n$ that marks the boundaries.

Lemma 3.6.

For an integer $1\leq\ell\leq(\log_{\sigma}n)/8$ , consider a set $\mathcal{C}\subseteq[0\mathop{.\,.}\sigma)^{\ell}$ . Given a text $T\in[0\mathop{.\,.}\sigma)^{n}$ and an ${\mathcal{O}}(1)$ -time membership oracle to $\mathcal{C}$ , a bitmask representing $\{i\in[0\mathop{.\,.}n-\ell]:T[i\mathop{.\,.}i+\ell)\in\mathcal{C}\}$ can be constructed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time.

Proof.

First, we construct an array $B[0\mathop{.\,.}\lfloor\sqrt{n}\rfloor)$ so that, for each string $U$ of length ${\ell\leq|U|\leq 2\ell\leq(\log_{\sigma}n)/4}$ , the entry $B[{\textnormal{{{int}}}}(U)]$ is a bitmask of length $|U|-\ell+1$ representing $\{i\in[0\mathop{.\,.}|U|-\ell]:U[i\mathop{.\,.}i+\ell)\in\mathcal{C}\}$ . Due to constant-time oracle access to $\mathcal{C}$ , the construction of $B$ takes ${\mathcal{O}}(\sqrt{n}\cdot\ell)={\tilde{{\mathcal{O}}}}(\sqrt{n})$ time.

Next, for each $j\in[0\mathop{.\,.}\lfloor n/\ell\rfloor)$ , we extract a string $T_{j}=T[j\ell\mathop{.\,.}\min(j\ell+2\ell-1,n))$ . In other words, this is a decomposition of $T$ into substrings of length $2\ell-1$ (with the last one of length between $\ell$ and $2\ell-1$ ) overlapping by exactly $\ell-1$ positions. Finally, we construct the resulting bitmask by concatenating the bitmasks $B[{\textnormal{{{int}}}}(T_{j})]$ for subsequent indices $[0\mathop{.\,.}\lfloor n/\ell\rfloor)$ . This is valid because, for each $i\in[0\mathop{.\,.}n-\ell]$ , we have $T[i\mathop{.\,.}i+\ell)=T_{\lfloor i/\ell\rfloor}[i\bmod\ell\mathop{.\,.}i% \bmod\ell+\ell)$ and the concatenated bitmasks are of length exactly $\ell$ (except for the last one, whose length is between $1$ and $\ell$ ). $\hfill\blacktriangleleft$

The well-known folklore Lemma below efficiently transforms a bitmask into an explicit set; a proof is provided for completeness.

Lemma 3.7.

Given a bitmask $M$ of length $n$ , the set $\{i\in[0\mathop{.\,.}n)\mid M[i]=1\}$ can be output in increasing order in ${\mathcal{O}}(n/\lg n+\sum_{i=0}^{n-1}M[i])$ time.

Proof.

We use a lookup table $L[0\mathop{.\,.}2^{\lfloor\lg n/2\rfloor})$ , where entry $L[x]$ contains a list of the one-bits in the binary representation of $x$ in left to right order. Clearly, the table can be computed in $\tilde{\mathcal{O}}(\sqrt{n})$ time. Then, we can process the mask $M$ in chunks of size $\lfloor\lg n/2\rfloor$ (padding the final chunk with zeros). For each chunk, we look up the list of one-bits and report them after applying the appropriate offset. This takes ${\mathcal{O}}(n/\lg n+\sum_{i=0}^{n-1}M[i])$ time. $\hfill\blacktriangleleft$

Lemma 3.8.

Given $T\in[0\mathop{.\,.}\sigma)^{n}$ and a parameter $k\in\mathbb{Z}_{\geq 0}$ , a set $\textnormal{{B}}_{k}$ (represented as a bitmask) satisfying the conditions of Proposition 2.1 can be constructed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time.

Proof.

If $k\leq K$ , the set $\textnormal{{C}}_{k}$ constructed in the proof of Lemma 3.5 serves as an ${\mathcal{O}}(1)$ -time membership oracle to the set of boundary contexts. We then convert $\textnormal{{C}}_{k}$ to $\textnormal{{B}}_{k}$ using Lemma 3.6 on the text $\texttt{\textdollar}^{\alpha_{k}}\cdot T\cdot\texttt{\textdollar}^{\alpha_{k}}$ , discarding the initial and final value (corresponding to positions $0$ and $n$ ). (Lemma 3.6 marks the leftmost position of each boundary context occurrence, and contexts are of length $2\alpha_{k}$ ; since position $i$ in $\texttt{\textdollar}^{\alpha_{k}}\cdot T\cdot\texttt{\textdollar}^{\alpha_{k}}$ corresponds to position $i-\alpha_{k}$ in $T$ , the reported positions are the central positions of boundary contexts in $T$ , as required.) If $k>K$ , we first construct the bitmask for $\textnormal{{B}}_{K}$ and then convert it into an explicit list of positions with Lemma 3.7. Then, we use Corollary 3.3 to obtain $\textnormal{{B}}_{k}$ in explicit representation in ${\mathcal{O}}({n/\log_{\sigma}n})$ time, which we convert back into a bitmask in ${\mathcal{O}}(n/\log n+\lvert\textnormal{{B}}_{k}\rvert)$ time. Due to $\lvert\textnormal{{B}}_{k}\rvert\leq\lvert\textnormal{{B}}_{K}\rvert={\mathcal% {O}}(n/\log_{\sigma}n)$ , the time is as claimed. $\hfill\blacktriangleleft$

Lemma 3.9.

A text $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given $k\in\mathbb{Z}_{\geq 0}$ , a set $\textnormal{{B}}_{k}$ satisfying the conditions of Proposition 2.1 can be constructed in ${\mathcal{O}}(1+n/\lambda_{k})$ time. The elements of $\textnormal{{B}}_{k}$ are reported from left to right.

Proof.

For $k\leq K$ , we can simply use Lemmas 3.8 and 3.7, which takes ${\mathcal{O}}(n/\log_{\sigma}n+\lvert\textnormal{{B}}_{k}\rvert)={\mathcal{O}}% (n/\lambda_{k})$ time. For all $k>K$ , the sets can be computed during preprocessing as follows. We compute $\textnormal{{B}}_{K}$ in explicit representation using Lemmas 3.8 and 3.7. Then, we obtain all the remaining sets using Corollary 3.3. $\hfill\blacktriangleleft$

4 Computing $\tau$ -Runs in Sublinear Time

An integer $p\in[1\mathop{.\,.}|S|]$ is a period of a string $S$ if $S[i]=S[i+p]$ holds for each $i\in[0\mathop{.\,.}|S|-p)$ . We denote the smallest period of a non-empty string $S$ by $\mathsf{per}(S)$ , and we call $S$ periodic whenever $\mathsf{per}(S)\leq\frac{1}{2}|S|$ .

A run (a maximal repetition) in a string $T$ is a periodic fragment $\gamma=T[i\mathop{.\,.}j)$ of $T$ that can be extended neither to the left nor to the right without increasing the smallest period $p=\mathsf{per}(\gamma)$ , i.e., $i=0$ or $T[i-1]\neq T[i+p-1]$ , and $j=n$ or $T[j]\neq T[j-p]$ . The set of all runs in $T$ is denoted by $\mathsf{RUNS}(T)$ . Crucially, the periodicity lemma [16] implies that distinct runs cannot overlap too much.

Fact 4.1 ([29, Lemma 1(ii)]).

Let $\gamma,\gamma^{\prime}\in\mathsf{RUNS}(T)$ be distinct yet overlapping runs in a string $T$ . If $p=\mathsf{per}(\gamma)$ and $p^{\prime}=\mathsf{per}(\gamma^{\prime})$ , then $|\gamma\cap\gamma^{\prime}|<p+p^{\prime}-\gcd(p,p^{\prime})$ .

Among many consequences of ˜4.1 is that every periodic fragment $T[i\mathop{.\,.}j)$ can be uniquely extended to a run $T[i^{\prime}\mathop{.\,.}j^{\prime})\in\mathsf{RUNS}(T)$ such that $i^{\prime}\leq i\leq j\leq j^{\prime}$ and $\mathsf{per}(T[i^{\prime}\mathop{.\,.}j^{\prime}))=\mathsf{per}(T[i\mathop{.\,% .}j))$ . We denote this unique extension by $\mathsf{run}(T[i\mathop{.\,.}j))$ . If $T[i\mathop{.\,.}j)$ is not periodic, we write $\mathsf{run}(T[i\mathop{.\,.}j))=\bot$ to indicate that the run extension is undefined.

Theorem 4.2 ([28, Theorem 1.5]).

A text $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given a fragment $x$ of $T$ , the run extension $\gamma=\mathsf{run}(x)$ can be computed in ${\mathcal{O}}(1)$ time. If $\gamma\neq\bot$ , then the query algorithm also returns the shortest period $\mathsf{per}(\gamma)=\mathsf{per}(x)$ .

For $\ell,p\in[0\mathop{.\,.}n]$ , we write $\mathsf{RUNS}_{\ell,p}(T)=\{\gamma\in\mathsf{RUNS}(T):|\gamma|\geq\ell\text{ % and }\mathsf{per}(\gamma)\leq p\}.$ The construction of string synchronizing sets relies on $\tau$ -runs defined for $\tau\in[1\mathop{.\,.}n]$ as

\mathsf{RUNS}_{\tau}(T)=\mathsf{RUNS}_{\tau,\lfloor\tau/3\rfloor}(T).

Proposition 4.3.

One can preprocess a text $T\in[0\mathop{.\,.}\sigma)^{n}$ in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given integers $\ell,p\in[0\mathop{.\,.}n]$ with $\ell\geq 2p$ , one can output the set $\mathsf{RUNS}_{\ell,p}(T)$ in ${\mathcal{O}}(n/(\ell+1-2p))$ time. The runs are reported together with their periods and simultaneously ordered by their start and end positions.

Proof.

In the preprocessing phase, we construct the data structure of Theorem 4.2. At query time, if $p=0$ , then we trivially return the empty set. Otherwise, we pick $\Delta=\ell+1-2p$ and, for $i\in[0\mathop{.\,.}\lfloor(n-2p)/\Delta\rfloor]$ , consider fragments $T_{i}=T[i\Delta\mathop{.\,.}i\Delta+2p)$ . For each $T_{i}$ , we compute $\gamma_{i}=\mathsf{run}(T_{i})$ and output $\gamma_{i}$ as long as $\gamma_{i}\neq\bot$ , $|\gamma_{i}|\geq\ell$ , and $\gamma_{i}\neq\gamma_{i-1}$ (or $i=0$ ). The query time is clearly ${\mathcal{O}}(n/\Delta)={\mathcal{O}}(n/(\ell+1-2p))$ . Correctness is easy to verify; for completeness, a proof is provided in the full version. $\hfill\blacktriangleleft$

Lemma 4.4.

For a text $T$ of length $n$ and integers $\ell,p\in[1\mathop{.\,.}n]$ , define

\mathsf{R}_{\ell,p}(T)=\{i\in[0\mathop{.\,.}n-\ell]:\mathsf{per}(T[i\mathop{.% \,.}i+\ell))\leq p\}.

If $\ell\geq 2p$ , then

\mathsf{RUNS}_{\ell,p}(T)=\{T[b\mathop{.\,.}e):[b\mathop{.\,.}e-\ell]\text{ is% a maximal interval contained in }\mathsf{R}_{\ell,p}(T)\}.

Proof.

Consider $\gamma=T[b\mathop{.\,.}e)\in\mathsf{RUNS}_{\ell,p}(T)$ . For each $i\in[b\mathop{.\,.}e-\ell]$ , the fragment $T[i\mathop{.\,.}i+\ell)$ is contained in $\gamma$ , and thus $\mathsf{per}(T[i\mathop{.\,.}i+\ell))\leq\mathsf{per}(\gamma)\leq p$ . Consequently, $[b\mathop{.\,.}e-\ell]\subseteq\mathsf{R}_{\ell,p}(T)$ .

Next, for a proof by contradiction, suppose that $b-1\in\mathsf{R}_{\ell,p}(T)$ . This means that $\mathsf{per}(T[b-1\mathop{.\,.}b+\ell-1))\leq p$ and thus $\gamma^{\prime}=\mathsf{run}(T[b-1\mathop{.\,.}b+\ell-1))\in\mathsf{RUNS}_{% \ell,p}(T)$ . The fragment $T[b\mathop{.\,.}b+\ell-1)$ is contained in both $\gamma$ and $\gamma^{\prime}$ , so the intersection of these two runs consists of at least $\ell-1\geq 2p-1\geq\mathsf{per}(\gamma)+\mathsf{per}(\gamma^{\prime})-\gcd(% \mathsf{per}(\gamma),\mathsf{per}(\gamma^{\prime}))$ positions. This contradicts ˜4.1, and thus $b-1\notin\mathsf{R}_{\ell,p}(T)$ . A symmetric argument shows that $e-\ell+1\notin\mathsf{R}_{\ell,p}(T)$ .

It remains to prove that every maximal interval $[i\mathop{.\,.}j]\subseteq\mathsf{R}_{\ell,p}(T)$ corresponds to a run $T[i\mathop{.\,.}j+\ell)\in\mathsf{RUNS}_{\ell,p}(T)$ . Since $i\in\mathsf{R}_{\ell,p}(T)$ , we have $\mathsf{per}(T[i\mathop{.\,.}i+\ell))\leq p$ , and thus $\gamma=\mathsf{run}(T[i\mathop{.\,.}i+\ell))\in\mathsf{RUNS}_{\ell,p}(T)$ . Denote $\gamma=T[b\mathop{.\,.}e)$ ; as previously shown, $[b\mathop{.\,.}e-\ell]$ is a maximal interval contained in $\mathsf{R}_{\ell,p}(T)$ . Since $i\in[b\mathop{.\,.}e-\ell]$ holds due to $b\leq i$ and $e\geq i+\ell$ and since $[i\mathop{.\,.}j]$ is also a maximal interval contained in $\mathsf{R}_{\ell,p}(T)$ , we conclude that $[i\mathop{.\,.}j]=[b\mathop{.\,.}e-\ell]$ , i.e., $T[b\mathop{.\,.}e)=T[i\mathop{.\,.}j+\ell)$ holds as claimed. $\hfill\blacktriangleleft$

Proposition 4.5.

Given a string $T\in[0\mathop{.\,.}\sigma)^{n}$ and parameters $\ell,p\in[0\mathop{.\,.}\lfloor(\log_{\sigma}n)/8\rfloor]$ , the bitmask $\mathsf{R}_{\ell,p}(T)$ can be constructed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time.

Proof.

Observe that, in ${\tilde{{\mathcal{O}}}}(\sqrt{n})$ time, we can construct a bitmask of length $\lfloor\sqrt{n}\rfloor$ whose set bits are $\{{\textnormal{{{int}}}}(R):R\in[0\mathop{.\,.}\sigma)^{\ell}\text{ and }% \mathsf{per}(R)\leq p\}$ . This gives us constant-time oracle access to the set $\{R\in[0\mathop{.\,.}\sigma)^{\ell}:\mathsf{per}(R)\leq p\}$ . Now, Lemma 3.6 lets us construct in ${\mathcal{O}}(n/\log_{\sigma}n)$ time a bitmask representing $\mathsf{R}_{\ell,p}(T)=\{i\in[0\mathop{.\,.}n-\ell]:\mathsf{per}(T[i\mathop{.% \,.}i+\ell))\leq p\}$ . The overall running time is ${\tilde{{\mathcal{O}}}}(\sqrt{n})+{\mathcal{O}}(n/\log_{\sigma}n)={\mathcal{O}% }(n/\log_{\sigma}n)$ . $\hfill\blacktriangleleft$

5 String Synchronizing Sets in Sublinear Time

Definition 5.1 (Synchronizing set [22]).

For a string $T[0\mathop{.\,.}n)$ and parameter $\tau\in[1\mathop{.\,.}\lfloor n/2\rfloor]$ , a set $\mathsf{Sync}\subseteq[0\mathop{.\,.}n-2\tau]$ is a $\tau$ -synchronizing set of $T$ if it satisfies the following two conditions:

Consistency:: For $i,j\in[0\mathop{.\,.}n-2\tau]$ , if $i\in\mathsf{Sync}$ and $T[i\mathop{.\,.}i+2\tau)\cong T[j\mathop{.\,.}j+2\tau)$ , then $j\in\mathsf{Sync}$ .
Density:: For $i\in[0\mathop{.\,.}n-3\tau+1]$ , we have $[i\mathop{.\,.}i+\tau)\cap\mathsf{Sync}=\emptyset$ if and only if $\mathsf{per}(T[i\mathop{.\,.}i+3\tau-1))\leq\frac{1}{3}\tau$ .

Proposition 5.2 ([28, Construction 3.5 and Lemma 5.2]).

For a string $T[0\mathop{.\,.}n)$ , let $(\textnormal{{B}}_{k})_{k\in\mathbb{Z}_{\geq 0}}$ be a descending chain satisfying Proposition 2.1. Consider a parameter $\tau\in[1\mathop{.\,.}\lfloor n/2\rfloor]$ .

Define a set $\mathsf{Sync}\subseteq[0\mathop{.\,.}n-2\tau]$ so that a position $i\in[0\mathop{.\,.}n-2\tau]$ belongs to $\mathsf{Sync}$ if and only if $\mathsf{per}(T[i\mathop{.\,.}i+2\tau))>\tfrac{1}{3}\tau$ and at least one of the following conditions holds:

$\blacksquare$

$i+\tau\in\textnormal{{B}}_{k(\tau)}$ , where $k(\tau)=\max\{j\in\mathbb{Z}_{\geq 0}\mid j=0\textnormal{ or }16\lambda_{j-1}% \leq\tau\}$ ;
$\blacksquare$

there exists a $\tau$ -run $T[b\mathop{.\,.}e)\in\mathsf{RUNS}_{\tau}(T)$ such that $b=i+1$ ; or
$\blacksquare$

there exists a $\tau$ -run $T[b\mathop{.\,.}e)\in\mathsf{RUNS}_{\tau}(T)$ such that $e=i+2\tau-1$ .

Then, $\mathsf{Sync}$ is a $\tau$ -synchronizing set of size $|\mathsf{Sync}|<\frac{70n}{\tau}$ .

Theorem 5.3 (Compare [28, Theorem 1.13]).

A string $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given $\tau\in[1\mathop{.\,.}\lfloor n/2\rfloor]$ , a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ of size $|\mathsf{Sync}|<\frac{70n}{\tau}$ can be constructed in ${\mathcal{O}}(\frac{n}{\tau})$ time. Moreover, $\mathsf{per}(T[i\mathop{.\,.}i+2\tau))>\frac{1}{3}\tau$ holds for every $i\in\mathsf{Sync}$ .

Proof.

We build $\mathsf{Sync}$ based on the construction specified in Proposition 5.2. At preprocessing time, we build an array of intervals $I[0\mathop{.\,.}k(n)]$ with $I[k]=\{\tau:k(\tau)=k\}$ . Note that $I[0]=[0\mathop{.\,.}\lceil 16\lambda_{0}\rceil)$ and $I[k]=[\lceil 16\lambda_{k-1}\rceil\mathop{.\,.}\lceil 16\lambda_{k}\rceil)$ for $k\in[1\mathop{.\,.}k(n)]$ . Since $k(n)={\mathcal{O}}(\lg n)$ and the values $\lambda_{j}$ can be computed in ${\mathcal{O}}(1)$ time each (using constant-time arithmetic operations on ${\mathcal{O}}(\lg n)$ -bit integers), this preprocessing takes ${\mathcal{O}}(\lg n)$ time. We also apply the ${\mathcal{O}}(n/\log_{\sigma}n)$ -time preprocessing of Lemmas 3.9 and 4.3.

Given $\tau$ , we first compute $k(\tau)$ by scanning $I[0\mathop{.\,.}k(n)]$ from the top down to find the largest $k$ with $\tau\in I[k]$ . This takes $1+k(n)-k(\tau)=1+{\mathcal{O}}(\lg\frac{n}{\tau})={\mathcal{O}}(\frac{n}{\tau})$ time. Next, we apply Lemma 3.9 to generate $\textnormal{{B}}_{k(\tau)}$ in ${\mathcal{O}}(1+n/\lambda_{k(\tau)})={\mathcal{O}}(n/\tau)$ time, where the definition of $k(\tau)$ implies $16\lambda_{k(\tau)}>\tau$ . Then, we use Proposition 4.3 to compute $\mathsf{RUNS}_{\tau}(T)$ , with runs simultaneously ordered by their start and end positions; this also takes ${\mathcal{O}}(n/\tau)$ time. Finally, we proceed exactly as in the proof of [28, Theorem 1.13], where it is shown how to derive $\mathsf{Sync}$ from $\textnormal{{B}}_{k(\tau)}$ and $\mathsf{RUNS}_{\tau}(T)$ in ${\mathcal{O}}(n/\tau)$ time. $\hfill\blacktriangleleft$

Theorem 5.4.

Given a string $T\in[0\mathop{.\,.}\sigma)^{n}$ and a parameter $\tau\in[1\mathop{.\,.}\lfloor n/2\rfloor]$ , a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ of size $|\mathsf{Sync}|<\frac{70n}{\tau}$ , represented as a bitmask, can be constructed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time. Moreover, $\mathsf{per}(T[i\mathop{.\,.}i+2\tau))>\frac{1}{3}\tau$ holds for every $i\in\mathsf{Sync}$ .

Proof.

If $\tau\geq(\log_{\sigma}n)/16$ , we apply Theorem 5.3 with preprocessing followed by a single query. In ${\mathcal{O}}(n/\log_{\sigma}n+n/\tau)={\mathcal{O}}(n/\log_{\sigma}n)$ time, this yields the explicit representation of the set $\mathsf{Sync}$ satisfying the desired conditions. We convert this set into a bitmask by starting with an all-0 bitmask and setting the $i$ -th bit for every $i\in\mathsf{Sync}$ . This conversion also takes ${\mathcal{O}}(n/\log_{\sigma}n+n/\tau)={\mathcal{O}}(n/\log_{\sigma}n)$ time.

In the complementary case of $\tau<(\log_{\sigma}n)/16$ , we first compute $k(\tau)$ in ${\mathcal{O}}(\lg n)$ time by naively iterating over all possibilities. Then, we apply Lemma 3.8 to compute a bitmask representing $\textnormal{{B}}_{k(\tau)}$ and Proposition 4.5 to compute bitmasks representing $\mathsf{R}_{2\tau,\lfloor\tau/3\rfloor}(T)$ and $\mathsf{R}_{\tau,\lfloor\tau/3\rfloor}(T)$ ; both subroutines take ${\mathcal{O}}(n/\log_{\sigma}n)$ time. According to Proposition 5.2, a synchronizing set satisfying the desired conditions can be obtained by including a position $i$ if and only if $\mathsf{per}(T[i\mathop{.\,.}i+2\tau))>\tau/3$ (which is equivalent to $i\notin\mathsf{R}_{2\tau,\lfloor\tau/3\rfloor}(T)$ ) and at least one of the following conditions hold:

$\blacksquare$

$i+\tau\in\textnormal{{B}}_{k(\tau)}$ ,
$\blacksquare$

there exists a $\tau$ -run $T[b\mathop{.\,.}e)\in\mathsf{RUNS}_{\tau}(T)$ such that $b=i+1$ (which, by Lemma 4.4, is equivalent to $i\notin\mathsf{R}_{\tau,\lfloor\tau/3\rfloor}(T)$ and $i+1\in\mathsf{R}_{\tau,\lfloor\tau/3\rfloor}(T)$ ),
$\blacksquare$

there exists a $\tau$ -run $T[b\mathop{.\,.}e)\in\mathsf{RUNS}_{\tau}(T)$ such that $e=i+2\tau-1$ (which, by Lemma 4.4, is equivalent to $i+\tau\notin\mathsf{R}_{\tau,\lfloor\tau/3\rfloor}(T)$ and $i+\tau-1\in\mathsf{R}_{\tau,\lfloor\tau/3\rfloor}(T)$ ).

Consequently, the bitmask representing $\mathsf{Sync}$ can be computed using ${\mathcal{O}}(1)$ bitwise operations (AND, OR, NOT) applied to the following components: $\mathsf{R}_{2\tau,\lfloor\tau/3\rfloor}$ ; the mask $\textnormal{{B}}_{k(\tau)}$ shifted by $\tau$ positions and padded with $0$ -bits; and four copies of $\mathsf{R}_{\tau,\lfloor\tau/3\rfloor}$ , shifted and padded as follows – by $0$ positions with $1$ -bits, by $1$ position with $0$ -bits, by $\tau-1$ positions with $0$ -bits, and by $\tau$ positions with $1$ -bits. All these bit-wise operations, including shifts and padding, can be implemented in ${\mathcal{O}}(n/\lg n)$ time, giving a total time of ${\mathcal{O}}(n/\log_{\sigma}n)$ . $\hfill\blacktriangleleft$

6 Improving the Query Time

In the remainder of the paper, we further improve the query time for synchronizing set construction from ${\mathcal{O}}(\frac{n}{\tau})$ to ${\mathcal{O}}(\frac{n\lg\tau}{\tau\lg n})$ , while retaining the ${\mathcal{O}}(n/\log_{\sigma}n)$ preprocessing time. We only outline the main algorithmic ideas here, with proofs of all claims in the full version.

The synchronizing set will be output in a representation of size ${\mathcal{O}}(\frac{n\lg\tau}{\tau})$ bits. We show that this is optimal in the lemma below, which models the query algorithm as a function mapping an input string $T$ into an encoding $\mathsf{E}(T)$ of a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ such that $\mathsf{Sync}$ can be recovered from $\mathsf{E}(T)$ alone using an accompanying decoding function $\mathsf{D}$ .

Lemma 6.1.

Consider integers $n,\tau\in\mathbb{Z}_{+}$ such that $n\geq 3\tau$ , as well as a pair of functions $\mathsf{E}:\{0,1\}^{n}\to\{0,1\}^{*}$ and $\mathsf{D}:\{0,1\}^{*}\to 2^{[0\mathop{.\,.}n)}$ jointly satisfying the following property:

For every $T\in\{0,1\}^{n}$ , the set $\mathsf{D}(\mathsf{E}(T))$ is a $\tau$ -synchronizing set of $T$ .

Then, there exists $T\in\{0,1\}^{n}$ such that $|\mathsf{E}(T)|=\Omega(\frac{n}{\tau}\lg\tau)$ .

Proof.

Let $k=\lfloor\frac{n}{3\tau}\rfloor$ . For an arbitrary string $S\in[0\mathop{.\,.}\tau)^{k}$ , we construct $T\in\{0,1\}^{n}$ defined by $\forall_{i\in[0\mathop{.\,.}k)}\;T[3\tau i\mathop{.\,.}3\tau i+3\tau):=\texttt% {0}^{2\tau+S[i]-1}\cdot\texttt{1}\cdot\texttt{0}^{\tau-S[i]}$ , with an arbitrary suffix $T[3\tau k\mathop{.\,.}n)$ . For any $\tau$ -synchronizing set, the first synchronizing position in $[3\tau i\mathop{.\,.}3\tau i+3\tau)$ is $3\tau i+S[i]$ . This holds due to Proposition 5.2 and the fact that $T[3\tau i\mathop{.\,.}3\tau i+2\tau+S[i]-1)$ is a suffix of a $\tau$ -run. Hence, given any $\tau$ -synchronizing set of $T$ , we can restore $S$ . Consequently, over all the $S\in[0\mathop{.\,.}\tau)^{k}$ , the average size of the encoded set is at least $k\lg\tau=\Omega(\frac{n}{\tau}\lg\tau)$ bits. $\hfill\blacktriangleleft$

Sparse encodings.

Our representation of the constructed $\tau$ -synchronizing set is its bitmask in a special sparse encoding. During the construction, we also encode intermediate integer arrays, and hence we give a more general definition. The encoding is based on Elias- $\gamma$ codes:

Definition 6.2 (Elias- $\gamma$ code [14]).

The Elias- $\gamma$ code of a positive integer $x\in\mathbb{Z}_{+}$ is a bitmask $\gamma(x):=\mathtt{0}^{\ell}\cdot X[0\mathop{.\,.}\ell]$ , where $\ell=\lfloor\lg x\rfloor$ and $X[0\mathop{.\,.}\ell]$ is the $(\ell+1)$ -bit binary representation of $x$ (with most significant bit $X[0]=\mathtt{1}$ ).

Definition 6.3 (Sparse encoding).

The sparse encoding of a string $A\in\mathbb{Z}_{\geq 0}^{n}$ is a bitmask $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ that encodes $A$ from left to right as follows. Each symbol $u\in\mathbb{Z}_{+}$ is stored as a literal token $\mathtt{1}\cdot\gamma(u)$ . Each inclusion-wise maximal fragment of the form $0^{x}$ for $x\in\mathbb{Z}_{+}$ is stored as a zero-run token $\mathtt{0}\cdot\gamma(x)$ .

Example 6.4.

Consider string $A=\texttt{000300500000009100}=\texttt{0}^{3}\cdot\texttt{3}\cdot\texttt{0}^{2}% \cdot\texttt{5}\cdot\texttt{0}^{7}\cdot\texttt{9}\cdot\texttt{1}\cdot\texttt{0% }^{2}$ and its sparse encoding shown below. The first bit of each token indicates whether it is a literal $x$ or a zero-run $\texttt{0}^{x}$ . The rest of the token consists of $\lfloor\lg x\rfloor$ zeros (to the left of each dotted line) and the binary representation of $x$ (to the right of each dotted line).

We note that a zero-run $\texttt{0}^{x}$ or a literal $x>0$ contributes $2\lfloor\lg x\rfloor+2$ bits to the encoding. By applying Jensen’s inequality to the concave log-function, we get the following bounds.

Observation 6.5.

For $A\in\mathbb{Z}_{\geq 0}^{n}$ , let $i_{1}<i_{2}<\dots<i_{a}$ be the elements of $\{i\in[0\mathop{.\,.}n)\mid A[i]\neq 0\}$ , and let $i_{0}=-1$ and $i_{a+1}=n$ . Regarding $\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert$ , we observe:

$\blacksquare$

The number of bits contributed by zero-run tokens is at most

$\textstyle 2a+2+\sum_{j=0}^{a}2\lfloor\lg(i_{j+1}-i_{j})\rfloor\in{\mathcal{O}% }((a+1)\cdot\lg\frac{n+1}{a+1})\subseteq{\mathcal{O}}(n).$
$\blacksquare$

The number of bits contributed by literal tokens is exactly

$\textstyle 2a+\sum_{j=1}^{a}2\lfloor\lg A[i_{j}]\rfloor\in{\mathcal{O}}(\sum_{% j=0}^{n-1}\lg(1+A[j]))\cap{\mathcal{O}}(a\cdot\lg(\frac{1}{a}\sum_{j=1}^{a}A[i% _{j}])).$
$\blacksquare$

If $\sum_{i=0}^{n-1}A[i]\in{\mathcal{O}}(n)$ , then $\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert\in{\mathcal{O}}((% a+1)\cdot\lg\frac{n+1}{a+1})$ .

If we encode the bitmask of a synchronizing set from Theorem 5.4, then the encoding consists of ${\mathcal{O}}(\lvert\mathsf{Sync}\rvert\cdot\lg\frac{n}{\lvert\mathsf{Sync}% \rvert})={\mathcal{O}}(\frac{n}{\tau}\lg\tau)$ bits. It is easy to see that the size of the encoding is minimized when the string $A$ is all-zero, in which case it consists of $2\lfloor\lg n\rfloor+2$ bits.

Observation 6.6.

For every $n\in\mathbb{Z}_{+}$ and $A\in\mathbb{Z}_{\geq_{0}}^{n}$ , it holds $2\lfloor\lg n\rfloor<\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert$ .

If a string $A$ is a prefix of another string $A^{\prime}$ , then the sparse encoding of $A$ is also a prefix of the sparse encoding of $A^{\prime}$ , unless $A$ ends with a zero-run that can be extended further in $A^{\prime}$ . In the latter case, the zero-run is encoded differently in $A$ and $A^{\prime}$ . Since the set of Elias- $\gamma$ codes (and hence the set of possible tokens) is prefix-free, this implies that the encoding of $A$ cannot be a prefix of the encoding of $A^{\prime}$ .

Observation 6.7.

The following holds for every two distinct non-empty strings $A,A^{\prime}\in\mathbb{Z}_{\geq 0}^{+}$ . The encoding $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ is a prefix of the encoding $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A^{\prime})$ if and only if $A$ is a prefix of $A^{\prime}$ and $A^{\prime}[\lvert A\rvert-1\mathop{.\,.}\lvert A\rvert]\neq 00$ .

Parsing sparse encodings.

We introduce basic tools for sparse encodings. Computing Elias- $\gamma$ codes can be accelerated with precomputed lookup tables. Then, we can encode and decode strings one token at a time, resulting in Lemma 6.9 below. For Lemma 6.9(ii), we merely split the computation time of Lemma 6.9(i) into preprocessing and query time.

Lemma 6.8.

For every $N\in[2\mathop{.\,.}2^{w}]$ , after an ${\mathcal{O}}(N)$ -time preprocessing, the following holds for every $u\in{{{\mathcal{O}}(w)}}$ and $x\in[1\mathop{.\,.}2^{u})$ . Computing $B:=\gamma(x)$ from the $u$ -bit representation of $x$ and computing the $u$ -bit representation of $x$ from a bitmask with prefix $B$ can be done in ${\mathcal{O}}(1+\lg x/\lg N)$ time. The size $\lvert B\rvert=2\lfloor\lg x\rfloor+1$ of the code is also reported.

Lemma 6.9.

For every $N\in[2\mathop{.\,.}2^{w}]$ , after an ${\mathcal{O}}(N)$ -time preprocessing, the following holds for every $u\in{\mathcal{O}}(w)$ . Let $A\in[0\mathop{.\,.}2^{u})^{n}$ with $n\in 2^{{\mathcal{O}}(w)}$ .

(i)

Computing the $u$ -bit representation of $A$ from $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ and vice versa can be done in ${\mathcal{O}}(n+\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert/% \lg N)$ time.
(ii)

If $A$ is given in $u$ -bit representation, then in ${\mathcal{O}}(n)$ time and space, one can compute a data structure that returns $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ in ${\mathcal{O}}(1+\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert/% \lg N)$ time.

We can encode and decode sparse arrays (in list representation) in constant time per non-zero entry, using Lemma 6.8 to process one token at a time.

Corollary 6.10.

After an ${\mathcal{O}}(\sqrt{n})$ -time preprocessing, given any array $A\in[0\mathop{.\,.}n^{{\mathcal{O}}(1)}]^{n}$ as a list of its $a\in[0\mathop{.\,.}n]$ non-zero entries as position-value pairs in increasing order of position, we can output $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ and vice versa in ${\mathcal{O}}(1+a)$ time.

6.1 Processing Sparse Encodings With Transducers

We will repeatedly process bitmasks, strings, and arrays in the sparse encoding. As a general tool for this task, we propose a preprocessing scheme for deterministic finite-state transducers, henceforth simply called transducers. A transducer consists of a finite set $Q$ of states, an initial state $s_{0}\in Q$ , a finite alphabet $\Sigma$ , and a transition function $\delta:Q\times\Sigma^{t}\rightarrow Q\times\Sigma$ . Given input strings $S_{1},\dots,S_{t}$ , the transducer produces output string $T$ , where all strings are of common length $n$ and are over alphabet $\Sigma$ . The computation is performed in a sequence of $n$ steps. Before the $i$ -th step (with $i\in[0\mathop{.\,.}n)$ ), the transducer is in state $s_{i}$ , and it has already written $T[0\mathop{.\,.}i)$ . The $i$ -th step is performed by evaluating $\delta(s_{i},S_{1}[i],\dots,S_{t}[i])=(s_{i+1},T[i])$ , resulting in the new state and the next symbol of the output string. Since the input strings are processed from left to right, we say that the transducer has $t$ input streams, and we call it a single-stream transducer if $t=1$ .

In the Theorem below, we show how to preprocess a single-stream transducer so that it can efficiently work directly on sparse encodings. For every state $s$ and every string $S^{\prime}$ for which $\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S^{\prime})\rvert$ is at most a small fraction of $\lg N$ , we precompute the entire chain of transitions performed when reading $S^{\prime}$ in state $s$ . The result of this precomputation is the new state reached after reading $S^{\prime}$ , as well as the sparse encoding of the produced output. This way, for a longer input encoding, we can process up to $\Omega(\lg N)$ bits in constant time.

Theorem 6.11.

Consider a single-stream transducer over alphabet $[0\mathop{.\,.}\sigma)$ with states $[0\mathop{.\,.}q)$ , where ${\sigma,q\in 2^{{\mathcal{O}}(w)}}$ . For every $N\in[2\mathop{.\,.}2^{w}]$ , if evaluating the transition function with input symbol $x$ (at any state) takes ${\mathcal{O}}(1+\lg(1+x)/\lg N)$ time, then after an ${\mathcal{O}}(qN)$ -time preprocessing, the following holds.

If $S$ is an input string of length $n\in 2^{{\mathcal{O}}(w)}$ for which the transducer produces output $T$ , then $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)$ can be computed from $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)$ in ${{\mathcal{O}}(1+{(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)% \rvert+\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)\rvert)/\lg N})}$ time.

Proof sketch.

We follow the full proof in the full version. Fix a small constant ${\varepsilon}>0$ and set $M=\Theta(N^{\varepsilon})$ to be a power of two (so $\lg M=\Theta(\lg N)$ ). The proof has two parts: (i) tabulate how the transducer behaves on all sparse encodings whose bit-length is $\leq\lg M$ , and (ii) process the remaining long tokens (especially long zero-runs) with a separate jumping mechanism.

Preprocessing.

We precompute information that lets us process $\Omega(\lg M)$ bits of the input encoding in ${\mathcal{O}}(1)$ time.

1.

Tabulating short prefixes of sparse encodings. For every state $s\in[0\mathop{.\,.}q)$ we build a lookup table $L_{s}$ indexed by all bitmasks $B\in\{0,1\}^{\lg M}$ . For each $B$ , we find the largest prefix length $b\leq\lg M$ such that $B[0\mathop{.\,.}b)$ is a sparse encoding. Let $A$ be the decoded length- $a$ string with $B[0\mathop{.\,.}b)=\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ . We simulate the transducer for $a$ steps on input $A$ , obtaining the new state $s^{\prime}$ and the produced output string $A^{\prime}$ . We then store in $L_{s}[{\textnormal{{{int}}}}(B)]$ (besides $b,a,s^{\prime}$ ) a representation of $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A^{\prime})$ that separates leading and trailing zeros: we keep the counts $z_{1},z_{2}$ of leading/trailing zeros of $A^{\prime}$ , and build the data structure $D$ from Lemma 6.9(ii) for the middle part $A^{\prime}[z_{1}\mathop{.\,.}a-z_{2})$ . This way, later we can append $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A^{\prime})$ to the global output in time ${\mathcal{O}}(1+\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A^{\prime}% )\rvert/\lg M)$ , without ever materializing it bit-by-bit. Computing a single entry takes ${\mathcal{O}}(1+a)$ time (decode $A$ , simulate $a$ transitions, and build $D$ ). Since $\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert\leq\lg M$ implies $a={\mathcal{O}}(M)$ by ˜6.6, the total for all $q M$ entries is ${\mathcal{O}}(qM^{2})$ .
2.

Short runs of input zeros. For each state $s$ , we also build a table that stores, for $y\in[0\mathop{.\,.}M^{1/4}]$ , the value $L^{\prime}_{s}[y]$ obtained by looking up $L_{s}$ on the $\lg M$ -bit word that starts with the sparse encoding of the zero-run token $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(0^{y})$ . This allows us to advance through $y$ consecutive input zeros in one constant-time lookup. The key point is that, for $y\leq M^{1/4}$ , the token $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(0^{y})$ has length $<\lg M$ , so it fits into one lookup word together with padding. If the tables $L_{s}$ are given, then the tables $L^{\prime}_{s}$ can be easily constructed in ${\mathcal{O}}(qM)$ time.
3.

Long stretches where input/output are both zero. Finally, for handling very long zero-run tokens, we build the directed graph on states in which there is an edge $s\to s^{\prime}$ iff the transducer transitions from $s$ to $s^{\prime}$ on input $0$ and outputs $0$ . This is a pseudoforest (outdegree $\leq 1$ ), so we can preprocess it with a simple adaptation of level ancestor queries [5] such that we can “jump” in ${\mathcal{O}}(1)$ time through long chains of transitions that keep outputting zero. Computing the graph and auxiliary data structure takes ${\mathcal{O}}(q)$ time.

Running the transducer on $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)$ .

Let $X:=\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)$ . As an invariant, we maintain: offsets $x\in[0\mathop{.\,.}\lvert X\rvert]$ and $n\in[0\mathop{.\,.}\lvert S\rvert]$ such that $X[0\mathop{.\,.}x)=\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S[0\mathop{.% \,.}n))$ , the current state $s$ reached by the transducer after processing $S[0\mathop{.\,.}n)$ , and an output representation consisting of (i) a counter $z$ that indicates the number of trailing zeros of $T[0\mathop{.\,.}n)$ and (ii) the sparse encoding $Y=\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T[0\mathop{.\,.}n-z))$ . Here, $Y$ is always a prefix of $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)$ due to ˜6.7. We process the remaining suffix $X[x\mathop{.\,.}]$ in macro-steps:

$\blacksquare$

If $L_{s}[X[x\mathop{.\,.}x+\lg M)]$ returns $b>0$ , then we have a whole sparse encoding $X[x\mathop{.\,.}x+b)=\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ fitting in $\lg M$ bits. We take the precomputed entry $(b,a,s^{\prime},z_{1},z_{2},D)$ and update $(x,n,s)$ by $(x+b,n+a,s^{\prime})$ . If the corresponding output $A^{\prime}$ is all-zero, we just increase $z$ . Otherwise we first flush the pending zeros by appending $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(0^{z+z_{1}})$ (if needed), then append the middle part via $D$ , and finally set $z\leftarrow z_{2}$ . Near the end of $X$ , we pad the $\lg M$ -bit window with an incomplete token to prevent decoding beyond $\lvert X\rvert$ .
$\blacksquare$

Otherwise $b=0$ , i.e., the next token of $X[x\mathop{.\,.}]$ is long (more than $\lg M$ bits). We decode this token (and its bit length $b^{\prime}$ ) using Lemma 6.8. If it is a literal, we decode the symbol, evaluate one transducer transition (cost ${\mathcal{O}}(1+\lg(1+x)/\lg N)$ by assumption), and append the encoded output symbol using Lemma 6.8. If, however, the decoded token is a zero-run token $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(0^{y})$ , then we handle it in a series of micro-steps. We alternate between (a) fixed micro-steps that advance by $M^{\prime}=\min(y,M^{1/4})$ using $L^{\prime}_{s}[M^{\prime}]$ (so we can also handle prefixes whose output is not all-zero), and (b) flexible micro-steps that use the precomputed graph and auxiliary data structure to skip a maximal prefix of transitions that read $0$ and output $0$ (advancing $n$ and increasing $z$ ). This continues until all $y$ input zeros are consumed. Finally, regardless of whether the decoded token is a literal or a zero-run token, we advance $x$ by $b^{\prime}$ bits.

Once we have processed the entire $X$ , we append $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(0^{z})$ to $Y$ , obtaining $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)$ .

Correctness.

By construction, each lookup-table entry faithfully simulates the transducer on the decoded prefix it represents, so using the tables updates the current state exactly as in the real run and produces exactly the corresponding output substring. The maintained invariant ensures that after every step, the processed part of $X$ corresponds to the processed prefix of the plain input, and $Y$ represents the output written so far up to the buffered trailing zeros. The only subtlety is concatenating outputs while preserving a valid sparse encoding; this is precisely why we keep trailing zeros in a counter $z$ and only flush them when the next chunk produces a non-zero output, using the prefix characterization in ˜6.7.

Time bound.

Each macro-step with $b>0$ advances the input encoding by a maximal sparse-encoding prefix inside a $\lg M$ -bit window; hence, any two consecutive macro-steps advance the input encoding by more than $\lg M$ bits (as otherwise, the steps could have been merged), and there are ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)\rvert/\lg M)$ macro-steps.

Micro-steps only occur inside long zero-run tokens. Every flexible micro-step advances the output to the next non-zero symbol. Therefore, for four consecutive micro-steps of the form (flexible, fixed, flexible, fixed), the first output symbol produced by each of the two fixed steps is a non-zero symbol. Hence, the encoding of the output produced by the central two steps is a substring of the encoding appended to $Y$ during the four steps. Also, by the definition of a fixed step, the (plain text) output corresponding to this substring is of length at least $M^{1/4}$ . By ˜6.6, its sparse encoding contains $\Omega(\lg M)$ bits, so (ignoring ${\mathcal{O}}(1)$ initial/final micro-steps per macro-step) we get ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)\rvert/\lg M)$ micro-steps overall. The number of initial/final micro-steps is limited by the number ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)\rvert/\lg M)$ of macro-steps.

Finally, whenever a step takes more than constant time, it is because, for some value $r$ , we (i) use Lemma 6.9(ii) to obtain an encoding consisting of $r$ bits and append it to the output, (ii) use Lemmas 6.8 and 6.8 to decode (resp. encode) a token consisting of $r$ bits and advance the input (resp. output) by $r$ bits, or (iii) evaluate a transition on a large literal whose encoding consists of $r$ bits. Each such cost is ${\mathcal{O}}(1+r/\lg M)$ , and it can be charged to the $\Theta(r)$ bits advanced in $X$ or appended to $Y$ , yielding total overhead ${\mathcal{O}}((\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)\rvert+% \lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)\rvert)/\lg M)$ . This gives total time ${\mathcal{O}}(1+(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)\rvert+% \lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)\rvert)/\lg M)={\mathcal% {O}}(1+(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)\rvert+\lvert% \mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)\rvert)/\lg N)$ . $\hfill\blacktriangleleft$

To handle multi-stream transducers, we use a reduction of multi-stream transducers to single-stream ones. For this purpose, we define a zipped string.

Definition 6.12.

Let $A_{1},\dots,A_{t}$ with $t\geq 1$ be strings in $\mathbb{Z}_{\geq 0}^{n}$ . The string $\textnormal{{zip}}(A_{1},\dots,A_{t})$ of length $n$ has, for each $i\in[0\mathop{.\,.}n)$ , its $i$ -th symbol defined by $\textnormal{{zip}}(A_{1},\dots,A_{t})[i]=0$ if $\forall_{j\in[1\mathop{.\,.}t]}\;A_{j}[i]=0$ , and $\textnormal{{zip}}(A_{1},\dots,A_{t})[i]=\mathsf{sp\smash{\underline{\phantom{% o}}}enc}(A_{1}[i]A_{2}[i]\dots A_{t}[i])$ otherwise.

We stress that this zipped string is not, in itself, a sparse encoding – it is a string in which each non-zero symbol is the sparsely encoded concatenation of the corresponding symbols of the original strings. Crucially, when sparsely encoding the zipped sequence, there is only a constant factor overhead over the sparsely encoded original strings.

Lemma 6.13.

Given a constant number of equal-length strings $A_{1},\dots,A_{t}\in\mathbb{Z}_{\geq 0}^{n}$ , it holds $\textstyle\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(\textnormal{{zip% }}(A_{1},\dots,A_{t}))\rvert={\mathcal{O}}(\sum_{j=1}^{t}\lvert\mathsf{sp% \smash{\underline{\phantom{o}}}enc}(A_{j})\rvert)$ .

Given the sparse encodings of the input strings, we first produce the sparse encoding of their zipped string. For the result below, we use similar techniques as in the proof of Theorem 6.11, processing up to $\Omega(\lg N)$ bits of the input encodings in constant time by exploiting precomputed information. Unlike in the proof of Theorem 6.11, a long synchronized run of zeros in the input strings always leads to a run of zeros in the output, simplifying the algorithm to some extent. However, non-synchronized runs of zeros pose an additional challenge, as described in detail in the full version.

Theorem 6.14.

For every $N\in[2\mathop{.\,.}2^{w}]$ , after an ${\mathcal{O}}(N)$ -time preprocessing, the following holds. If $A_{1},\dots,A_{t}\in[0\mathop{.\,.}\sigma)^{n}$ with $t={\mathcal{O}}(1)$ and $n,\sigma\in{2^{{\mathcal{O}}(w)}}$ , then $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(\textnormal{{zip}}(A_{1},\dots,A% _{t}))$ can be computed from $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A_{1}),\dots,\mathsf{sp\smash{% \underline{\phantom{o}}}enc}(A_{t})$ in ${\mathcal{O}}(1+\sum_{j=1}^{t}\lvert\mathsf{sp\smash{\underline{\phantom{o}}}% enc}(A_{j})\rvert/\lg N)$ time.

Finally, there is an obvious reduction from a transducer with $t$ input strings to a single-stream transducer that receives the zipped version of the $t$ input strings. By applying Theorem 6.11 to this single-stream transducer, we obtain the following result.

Corollary 6.15.

Consider a transducer over alphabet $[0\mathop{.\,.}\sigma)$ with states $[0\mathop{.\,.}q)$ , where ${\sigma,q\in 2^{{\mathcal{O}}(w)}}$ , and $t={\mathcal{O}}(1)$ input streams. If the transition function can be evaluated in ${\mathcal{O}}(1)$ time, then, for any $N\in[2\mathop{.\,.}2^{w}]$ , after an ${\mathcal{O}}(qN)$ -time preprocessing, the following holds.

Let $S_{1},\dots,S_{t}$ be input strings of common length $n\in 2^{{\mathcal{O}}(w)}$ for which the transducer produces output $T$ . Then $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)$ can be computed from $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S_{1}),\dots,\mathsf{sp\smash{% \underline{\phantom{o}}}enc}(S_{t})$ in ${{\mathcal{O}}((\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(T)\rvert+% \sum_{i=1}^{t}\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S_{i})\rvert% )/\lg N)}$ time.

6.2 Faster Synchronizing Set Queries

Using Corollary 6.15, we obtain sparsely encoded versions of the sets $\textnormal{{B}}_{k}$ , of $\mathsf{RUNS}_{\tau,\lfloor\tau/3\rfloor}(T)$ and $\mathsf{RUNS}_{2\tau,\lfloor\tau/3\rfloor}(T)$ , and finally of a $\tau$ -synchronizing set. Ultimately, we derive the following.

Theorem 6.16.

A string $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given $\tau\in[1\mathop{.\,.}\lfloor n/2\rfloor]$ , a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ of size $|\mathsf{Sync}|<\frac{70n}{\tau}$ can be constructed in ${\mathcal{O}}(\frac{n\lg\tau}{\tau\lg n})$ time and ${\mathcal{O}}(\frac{n\lg\tau}{\tau})$ bits of space. The set is reported as $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(M)$ for $M\in\{0,1\}^{n}$ such that $M[i]=1\Leftrightarrow i\in\mathsf{Sync}$ . Moreover, $\mathsf{per}(T[i\mathop{.\,.}i+2\tau))>\frac{1}{3}\tau$ holds for every $i\in\mathsf{Sync}$ .

6.3 Adding Rank and Select Support

Theorem 6.16 returns the synchronizing set in sparse encoding, which by itself does not allow fast random access. Hence, we develop support data structures that augment the encoding for fast rank and select queries. For any set $S\subseteq\mathbb{Z}$ and $x\in\mathbb{Z}_{\geq 0}$ , we define $\textup{{rank}}_{S}(x)=\lvert\{y\in S\mid y<x\}\rvert$ and $\textup{{pred}}_{S}(x)=\max(\{y\in S\mid y\leq x\}\cup\{-\infty\})$ . For every $i\in[1\mathop{.\,.}\lvert S\rvert]$ , we define $\textup{{select}}_{S}(i)=\max\{y\in S\mid\textup{{rank}}_{S}(y)<i\}$ . For $S\subseteq[0\mathop{.\,.}U)$ and its characteristic bitmask $A[0\mathop{.\,.}U)$ , we may equivalently use subscript $A$ rather than $S$ .

We can use a precomputed lookup table to greedily parse any encoding into pieces of size around $\lg N$ bits, and then use another table to answer rank and select queries with respect to any piece in constant time. This is formalized below.

Lemma 6.17.

For every $N\in[5\mathop{.\,.}2^{w}]$ and every bitmask $A[0\mathop{.\,.}n)$ , there is a sequence $(i,p_{i},e_{i},r_{i})_{i=0}^{h}$ with $h={\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert/% \lg N)$ satisfying the following properties. The entries are defined by $p_{0}=e_{0}=0$ , $p_{h}=n$ , $e_{h}=\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert$ , and, for $i\in[0\mathop{.\,.}h)$ ,

$\blacksquare$

$\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)[e_{i}\mathop{.\,.}e_{i+1})=% \mathsf{sp\smash{\underline{\phantom{o}}}enc}(A[p_{i}\mathop{.\,.}p_{i+1}))$ and $r_{i}=\textup{{rank}}_{A}(p_{i})$ , and
$\blacksquare$

either $A[p_{i}\mathop{.\,.}p_{i+1})$ is all-zero, or $r_{i+1}-r_{i}\leq e_{i+1}-e_{i}\leq\lg N$ .

After a $\tilde{\mathcal{O}}(N)$ time preprocessing, the following holds. Given $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ , the sequence can be computed in ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert/\lg N)$ time and ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert% \cdot\lg n/\lg N)$ bits of space. In the same time and space, we can compute a data structure that,

$\blacksquare$

given $i\in[0\mathop{.\,.}h]$ and $j\in[p_{i}\mathop{.\,.}p_{i+1})$ , returns $\textup{{rank}}_{A}(j)$ in constant time, and
$\blacksquare$

given $i\in[0\mathop{.\,.}h]$ and $j\in(r_{i}\mathop{.\,.}r_{i+1}]$ , returns $\textup{{select}}_{A}(j)$ in constant time.

Now, to answer a query $\textup{{select}}_{A}(j)$ , we only have to find the unique tuple of the decomposition with $r_{i}<j\leq r_{i+1}$ . This can be done via two auxiliary bitmasks of length $\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert$ that respectively mark the starting positions of literal tokens in $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ and the positions $e_{i}$ of all the tuples. Then, we can find the correct tuples via rank and select queries on the auxiliary bitmasks. Crucially, we can use existing data structures for constant time rank and select support on these bitmasks [4].

Lemma 6.18.

For every $N\in[5\mathop{.\,.}2^{w}]$ , after a $\tilde{\mathcal{O}}(N)$ time preprocessing, the following holds. Given a sparse encoding $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ of a bitmask $A[0\mathop{.\,.}n)$ with $n\in 2^{{\mathcal{O}}(w)}$ and $\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert={\mathcal{O}}(% \textnormal{poly}(N))$ , we can compute a data structure for ${\mathcal{O}}(1)$ time select queries in ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert/\lg N)$ time and ${\mathcal{O}}(\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert% \cdot(1+\lg n/\lg N))$ bits of space.

For implementing rank support, we rely on an improved version of van Emde Boas trees [42] given in the Theorem below. It is well known that the claimed complexities can be achieved with expected construction time and space [33, 34]. Our deterministic solution can be obtained by essentially replacing the hash tables of van Emde Boas trees with deterministic dictionaries [37]. For completeness, we give a detailed description in the full version.

Theorem 1.3. [Restated, see original statement.]

Let $S\subseteq[0\mathop{.\,.}2^{\ell})$ of size $\lvert S\rvert=n$ with $\ell\geq 2$ and $n,2^{\ell}\in 2^{{\mathcal{O}}(w)}$ be given as an array of $\ell$ -bit integers in increasing order. For $m\geq n$ , let $a=\lg(m/n)+\lg w$ . A deterministic data structure that answers rank and predecessor queries in ${\mathcal{O}}(\lg\frac{\ell-\lg m}{a})$ time can be built in ${\mathcal{O}}(m)$ time and words of space.

We construct this data structure for the sequence $p_{0},\dots,p_{h}$ from Lemma 6.17, simulating words of width $w=\Theta(\lg n)$ . This way, for a query $\textup{{rank}}_{A}(j)$ , we can find the unique $i$ such that $j\in[p_{i}\mathop{.\,.}p_{i+1})$ , allowing us to answer the query with Lemma 6.17.

Lemma 6.19.

For every $N\in[5\mathop{.\,.}2^{w}]$ , after a $\tilde{\mathcal{O}}(N)$ time preprocessing, the following holds. Given a sparse encoding $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)$ of a bitmask $A[0\mathop{.\,.}n)$ with $n\in 2^{{\mathcal{O}}(w)}$ and a parameter $m\geq\lvert\mathsf{sp\smash{\underline{\phantom{o}}}enc}(A)\rvert/\lg{N}$ , we can compute a data structure for ${\mathcal{O}}(\lg\frac{\lg n-\lg m}{\lg\lg n})$ time rank and predecessor queries in ${\mathcal{O}}(m)$ time and ${\mathcal{O}}(m\lg n)$ bits of space.

Finally, by combining Theorem 6.16 with Lemma 6.18 and Lemma 6.19 with parameter $m=\Theta(\frac{n\lg\tau}{\tau\lg n})$ , we obtain the following main result.

Corollary 6.20.

A string $T\in[0\mathop{.\,.}\sigma)^{n}$ can be preprocessed in ${\mathcal{O}}(n/\log_{\sigma}n)$ time so that, given $\tau\in[1\mathop{.\,.}\lfloor n/2\rfloor]$ , a $\tau$ -synchronizing set $\mathsf{Sync}$ of $T$ of size $|\mathsf{Sync}|<\frac{70n}{\tau}$ can be constructed in ${\mathcal{O}}(\frac{n\lg\tau}{\tau\lg n})$ time. The set is reported in a representation of size ${\mathcal{O}}(\frac{n\lg\tau}{\tau})$ bits that supports select queries in constant time, and rank queries in ${\mathcal{O}}(\lg\frac{\lg\tau}{\lg\lg n})$ time.

References

[1] Shyan Akmal and Ce Jin. Near-optimal quantum algorithms for string problems. Algorithmica, 85(8):2260–2317, 2023. doi:10.1007/S00453-022-01092-X.
[2] Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Waleń, and Wiktor Zuba. Quasi-linear-time algorithm for longest common circular factor. In Nadia Pisanti and Solon P. Pissis, editors, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy, volume 128 of LIPIcs, pages 25:1–25:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CPM.2019.25.
[3] Lorraine A. K. Ayad, Grigorios Loukides, and Solon P. Pissis. Text indexing for long patterns using locally consistent anchors. VLDB J., 34(5):58, 2025. doi:10.1007/S00778-025-00935-7.
[4] Maxim A. Babenko, Paweł Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya. Wavelet trees meet suffix trees. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 572–591. SIAM, 2015. doi:10.1137/1.9781611973730.39.
[5] Michael A. Bender and Martin Farach-Colton. The level ancestor problem simplified. Theor. Comput. Sci., 321(1):5–12, 2004. doi:10.1016/J.TCS.2003.05.002.
[6] Or Birenzwige, Shay Golan, and Ely Porat. Locally consistent parsing for text indexing in small space. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 607–626. SIAM, 2020. doi:10.1137/1.9781611975994.37.
[7] Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, and Taher Mun. Prefix-free parsing for building big BWTs. Algorithms Mol. Biol., 14(1):13:1–13:15, 2019. doi:10.1186/S13015-019-0148-5.
[8] Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Faster algorithms for longest common substring. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 30:1–30:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ESA.2021.30.
[9] Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Counting distinct square substrings in sublinear time. In Paweł Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, August 25-29, 2025, Warsaw, Poland, volume 345 of LIPIcs, pages 36:1–36:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.MFCS.2025.36.
[10] Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski. Longest palindromic substring in sublinear time. In Hideo Bannai and Jan Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, volume 223 of LIPIcs, pages 20:1–20:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CPM.2022.20.
[11] Graham Cormode and S. Muthukrishnan. Substring compression problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 321–330. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070478.
[12] Graham Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. ACM Trans. Algorithms, 3(1):2:1–2:19, 2007. doi:10.1145/1219944.1219947.
[13] Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, and Florian Kurpicz. Practical performance of space efficient data structures for longest common extensions. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 39:1–39:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ESA.2020.39.
[14] Peter Elias. Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory, 21(2):194–203, 1975. doi:10.1109/TIT.1975.1055349.
[15] Jonas Ellert. Sublinear time Lempel-Ziv (LZ77) factorization. In Franco Maria Nardini, Nadia Pisanti, and Rossano Venturini, editors, String Processing and Information Retrieval - 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26-28, 2023, Proceedings, volume 14240 of Lecture Notes in Computer Science, pages 171–187. Springer, 2023. doi:10.1007/978-3-031-43980-3_14.
[16] N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16:109–114, 1965. doi:10.1090/S0002-9939-1965-0174934-9.
[17] Ragnar Groot Koerkamp. Optimal Throughput Bioinformatics. PhD thesis, ETH Zurich, 2025. doi:10.3929/ethz-c-000783091.
[18] Torben Hagerup. Sorting and searching on the word RAM. In Michel Morvan, Christoph Meinel, and Daniel Krob, editors, STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings, volume 1373 of Lecture Notes in Computer Science, pages 366–398. Springer, 1998. doi:10.1007/BFB0028575.
[19] Artur Jeż. Approximation of grammar-based compression via recompression. Theor. Comput. Sci., 592:115–134, 2015. doi:10.1016/J.TCS.2015.05.027.
[20] Artur Jeż. Recompression: A simple and powerful technique for word equations. J. ACM, 63(1):4:1–4:51, 2016. doi:10.1145/2743014.
[21] Ce Jin and Jakob Nogler. Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching. ACM Trans. Algorithms, 20(4):32:1–32:36, 2024. doi:10.1145/3672395.
[22] Dominik Kempa and Tomasz Kociumaka. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 756–767. ACM, 2019. doi:10.1145/3313276.3316368.
[23] Dominik Kempa and Tomasz Kociumaka. Dynamic suffix array with polylogarithmic queries and updates. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1657–1670. ACM, 2022. doi:10.1145/3519935.3520061.
[24] Dominik Kempa and Tomasz Kociumaka. Resolution of the Burrows-Wheeler transform conjecture. Commun. ACM, 65(6):91–98, 2022. doi:10.1145/3531445.
[25] Dominik Kempa and Tomasz Kociumaka. Breaking the ${O}(n)$ -barrier in the construction of compressed suffix arrays and suffix trees. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5122–5202. SIAM, 2023. doi:10.1137/1.9781611977554.CH187.
[26] Dominik Kempa and Tomasz Kociumaka. Lempel-Ziv (LZ77) factorization in sublinear time. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 2045–2055. IEEE, 2024. doi:10.1109/FOCS61266.2024.00122.
[27] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Internal pattern matching queries in a text and applications. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 532–551. SIAM, 2015. doi:10.1137/1.9781611973730.36.
[28] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Internal pattern matching queries in a text and applications. SIAM J. Comput., 53(5):1524–1577, 2024. doi:10.1137/23M1567618.
[29] Roman M. Kolpakov and Gregory Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999, pages 596–604. IEEE Computer Society, 1999. doi:10.1109/SFFCS.1999.814634.
[30] Grigorios Loukides and Solon P. Pissis. Bidirectional string anchors: A new string sampling mechanism. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 64:1–64:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ESA.2021.64.
[31] Mamoru Maekawa. A square root N algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst., 3(2):145–159, 1985. doi:10.1145/214438.214445.
[32] Kurt Mehlhorn, R. Sundar, and Christian Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183–198, 1997. doi:10.1007/BF02522825.
[33] Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 232–240. ACM, 2006. doi:10.1145/1132516.1132551.
[34] Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search, 2006. doi:10.48550/arXiv.cs/0603043.
[35] Jakub Radoszewski and Wiktor Zuba. Computing string covers in sublinear time. In Zsuzsanna Lipták, Edleno Silva de Moura, Karina Figueroa, and Ricardo Baeza-Yates, editors, String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Puerto Vallarta, Mexico, September 23-25, 2024, Proceedings, volume 14899 of Lecture Notes in Computer Science, pages 272–288. Springer, 2024. doi:10.1007/978-3-031-72200-4_21.
[36] Michael Roberts, Wayne Hayes, Brian R. Hunt, Stephen M. Mount, and James A. Yorke. Reducing storage requirements for biological sequence comparison. Bioinformatics, 20(18):3363–3369, 2004. doi:10.1093/bioinformatics/bth408.
[37] Milan Ruzic. Constructing efficient dictionaries in close to sorting time. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 84–95. Springer, 2008. doi:10.1007/978-3-540-70575-8_8.
[38] Süleyman Cenk Sahinalp and Uzi Vishkin. On a parallel-algorithms method for string matching problems. In Maurizio A. Bonuccelli, Pierluigi Crescenzi, and Rossella Petreschi, editors, Algorithms and Complexity, Second Italian Conference, CIAC ’94, Rome, Italy, February 23-25, 1994, Proceedings, volume 778 of Lecture Notes in Computer Science, pages 22–32. Springer, 1994. doi:10.1007/3-540-57811-0_3.
[39] Süleyman Cenk Sahinalp and Uzi Vishkin. Symmetry breaking for suffix tree construction. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 300–309. ACM, 1994. doi:10.1145/195058.195164.
[40] Süleyman Cenk Sahinalp and Uzi Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm (extended abstract). In 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14-16 October, 1996, pages 320–328. IEEE Computer Society, 1996. doi:10.1109/SFCS.1996.548491.
[41] Saul Schleimer, Daniel Shawcross Wilkerson, and Alex Aiken. Winnowing: Local algorithms for document fingerprinting. In Alon Y. Halevy, Zachary G. Ives, and AnHai Doan, editors, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pages 76–85. ACM, 2003. doi:10.1145/872757.872770.
[42] Peter van Emde Boas. Preserving order in a forest in less than logarithmic time. In 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, pages 75–84. IEEE Computer Society, 1975. doi:10.1109/SFCS.1975.26.

[bib.bib1] [1] Shyan Akmal and Ce Jin. Near-optimal quantum algorithms for string problems. Algorithmica, 85(8):2260–2317, 2023. doi:10.1007/S00453-022-01092-X.

[bib.bib2] [2] Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Waleń, and Wiktor Zuba. Quasi-linear-time algorithm for longest common circular factor. In Nadia Pisanti and Solon P. Pissis, editors, 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy, volume 128 of LIPIcs, pages 25:1–25:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CPM.2019.25.

[bib.bib3] [3] Lorraine A. K. Ayad, Grigorios Loukides, and Solon P. Pissis. Text indexing for long patterns using locally consistent anchors. VLDB J., 34(5):58, 2025. doi:10.1007/S00778-025-00935-7.

[bib.bib4] [4] Maxim A. Babenko, Paweł Gawrychowski, Tomasz Kociumaka, and Tatiana Starikovskaya. Wavelet trees meet suffix trees. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 572–591. SIAM, 2015. doi:10.1137/1.9781611973730.39.

[bib.bib5] [5] Michael A. Bender and Martin Farach-Colton. The level ancestor problem simplified. Theor. Comput. Sci., 321(1):5–12, 2004. doi:10.1016/J.TCS.2003.05.002.

[bib.bib6] [6] Or Birenzwige, Shay Golan, and Ely Porat. Locally consistent parsing for text indexing in small space. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 607–626. SIAM, 2020. doi:10.1137/1.9781611975994.37.

[bib.bib7] [7] Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, and Taher Mun. Prefix-free parsing for building big BWTs. Algorithms Mol. Biol., 14(1):13:1–13:15, 2019. doi:10.1186/S13015-019-0148-5.

[bib.bib8] [8] Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Faster algorithms for longest common substring. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 30:1–30:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ESA.2021.30.

[bib.bib9] [9] Panagiotis Charalampopoulos, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń, and Wiktor Zuba. Counting distinct square substrings in sublinear time. In Paweł Gawrychowski, Filip Mazowiecki, and Michal Skrzypczak, editors, 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, August 25-29, 2025, Warsaw, Poland, volume 345 of LIPIcs, pages 36:1–36:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.MFCS.2025.36.

[bib.bib10] [10] Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski. Longest palindromic substring in sublinear time. In Hideo Bannai and Jan Holub, editors, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, volume 223 of LIPIcs, pages 20:1–20:9. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.CPM.2022.20.

[bib.bib11] [11] Graham Cormode and S. Muthukrishnan. Substring compression problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 321–330. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070478.

[bib.bib12] [12] Graham Cormode and S. Muthukrishnan. The string edit distance matching problem with moves. ACM Trans. Algorithms, 3(1):2:1–2:19, 2007. doi:10.1145/1219944.1219947.

[bib.bib13] [13] Patrick Dinklage, Johannes Fischer, Alexander Herlez, Tomasz Kociumaka, and Florian Kurpicz. Practical performance of space efficient data structures for longest common extensions. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 39:1–39:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.ESA.2020.39.

[bib.bib14] [14] Peter Elias. Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory, 21(2):194–203, 1975. doi:10.1109/TIT.1975.1055349.

[bib.bib15] [15] Jonas Ellert. Sublinear time Lempel-Ziv (LZ77) factorization. In Franco Maria Nardini, Nadia Pisanti, and Rossano Venturini, editors, String Processing and Information Retrieval - 30th International Symposium, SPIRE 2023, Pisa, Italy, September 26-28, 2023, Proceedings, volume 14240 of Lecture Notes in Computer Science, pages 171–187. Springer, 2023. doi:10.1007/978-3-031-43980-3_14.

[bib.bib16] [16] N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16:109–114, 1965. doi:10.1090/S0002-9939-1965-0174934-9.

[bib.bib17] [17] Ragnar Groot Koerkamp. Optimal Throughput Bioinformatics. PhD thesis, ETH Zurich, 2025. doi:10.3929/ethz-c-000783091.

[bib.bib18] [18] Torben Hagerup. Sorting and searching on the word RAM. In Michel Morvan, Christoph Meinel, and Daniel Krob, editors, STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings, volume 1373 of Lecture Notes in Computer Science, pages 366–398. Springer, 1998. doi:10.1007/BFB0028575.

[bib.bib19] [19] Artur Jeż. Approximation of grammar-based compression via recompression. Theor. Comput. Sci., 592:115–134, 2015. doi:10.1016/J.TCS.2015.05.027.

[bib.bib20] [20] Artur Jeż. Recompression: A simple and powerful technique for word equations. J. ACM, 63(1):4:1–4:51, 2016. doi:10.1145/2743014.

[bib.bib21] [21] Ce Jin and Jakob Nogler. Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching. ACM Trans. Algorithms, 20(4):32:1–32:36, 2024. doi:10.1145/3672395.

[bib.bib22] [22] Dominik Kempa and Tomasz Kociumaka. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 756–767. ACM, 2019. doi:10.1145/3313276.3316368.

[bib.bib23] [23] Dominik Kempa and Tomasz Kociumaka. Dynamic suffix array with polylogarithmic queries and updates. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1657–1670. ACM, 2022. doi:10.1145/3519935.3520061.

[bib.bib24] [24] Dominik Kempa and Tomasz Kociumaka. Resolution of the Burrows-Wheeler transform conjecture. Commun. ACM, 65(6):91–98, 2022. doi:10.1145/3531445.

[bib.bib25] [25] Dominik Kempa and Tomasz Kociumaka. Breaking the ${O}(n)$ -barrier in the construction of compressed suffix arrays and suffix trees. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5122–5202. SIAM, 2023. doi:10.1137/1.9781611977554.CH187.

[bib.bib26] [26] Dominik Kempa and Tomasz Kociumaka. Lempel-Ziv (LZ77) factorization in sublinear time. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 2045–2055. IEEE, 2024. doi:10.1109/FOCS61266.2024.00122.

[bib.bib27] [27] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Internal pattern matching queries in a text and applications. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 532–551. SIAM, 2015. doi:10.1137/1.9781611973730.36.

[bib.bib28] [28] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. Internal pattern matching queries in a text and applications. SIAM J. Comput., 53(5):1524–1577, 2024. doi:10.1137/23M1567618.

[bib.bib29] [29] Roman M. Kolpakov and Gregory Kucherov. Finding maximal repetitions in a word in linear time. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999, pages 596–604. IEEE Computer Society, 1999. doi:10.1109/SFFCS.1999.814634.

[bib.bib30] [30] Grigorios Loukides and Solon P. Pissis. Bidirectional string anchors: A new string sampling mechanism. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 64:1–64:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ESA.2021.64.

[bib.bib31] [31] Mamoru Maekawa. A square root N algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst., 3(2):145–159, 1985. doi:10.1145/214438.214445.

[bib.bib32] [32] Kurt Mehlhorn, R. Sundar, and Christian Uhrig. Maintaining dynamic sequences under equality tests in polylogarithmic time. Algorithmica, 17(2):183–198, 1997. doi:10.1007/BF02522825.

[bib.bib33] [33] Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 232–240. ACM, 2006. doi:10.1145/1132516.1132551.

[bib.bib34] [34] Mihai Pătraşcu and Mikkel Thorup. Time-space trade-offs for predecessor search, 2006. doi:10.48550/arXiv.cs/0603043.

[bib.bib35] [35] Jakub Radoszewski and Wiktor Zuba. Computing string covers in sublinear time. In Zsuzsanna Lipták, Edleno Silva de Moura, Karina Figueroa, and Ricardo Baeza-Yates, editors, String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Puerto Vallarta, Mexico, September 23-25, 2024, Proceedings, volume 14899 of Lecture Notes in Computer Science, pages 272–288. Springer, 2024. doi:10.1007/978-3-031-72200-4_21.

[bib.bib36] [36] Michael Roberts, Wayne Hayes, Brian R. Hunt, Stephen M. Mount, and James A. Yorke. Reducing storage requirements for biological sequence comparison. Bioinformatics, 20(18):3363–3369, 2004. doi:10.1093/bioinformatics/bth408.

[bib.bib37] [37] Milan Ruzic. Constructing efficient dictionaries in close to sorting time. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Track A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 84–95. Springer, 2008. doi:10.1007/978-3-540-70575-8_8.

[bib.bib38] [38] Süleyman Cenk Sahinalp and Uzi Vishkin. On a parallel-algorithms method for string matching problems. In Maurizio A. Bonuccelli, Pierluigi Crescenzi, and Rossella Petreschi, editors, Algorithms and Complexity, Second Italian Conference, CIAC ’94, Rome, Italy, February 23-25, 1994, Proceedings, volume 778 of Lecture Notes in Computer Science, pages 22–32. Springer, 1994. doi:10.1007/3-540-57811-0_3.

[bib.bib39] [39] Süleyman Cenk Sahinalp and Uzi Vishkin. Symmetry breaking for suffix tree construction. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 300–309. ACM, 1994. doi:10.1145/195058.195164.

[bib.bib40] [40] Süleyman Cenk Sahinalp and Uzi Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm (extended abstract). In 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14-16 October, 1996, pages 320–328. IEEE Computer Society, 1996. doi:10.1109/SFCS.1996.548491.

[bib.bib41] [41] Saul Schleimer, Daniel Shawcross Wilkerson, and Alex Aiken. Winnowing: Local algorithms for document fingerprinting. In Alon Y. Halevy, Zachary G. Ives, and AnHai Doan, editors, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, June 9-12, 2003, pages 76–85. ACM, 2003. doi:10.1145/872757.872770.

[bib.bib42] [42] Peter van Emde Boas. Preserving order in a forest in less than logarithmic time. In 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, pages 75–84. IEEE Computer Society, 1975. doi:10.1109/SFCS.1975.26.

Time-Optimal Construction of String Synchronizing Sets

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.1 (Simplified version of Theorem 5.3).

Theorem 1.2 (Simplified version of Corollary 6.20).

Our Techniques.

Theorem 1.3.

Applications of Synchronizing Sets.

Other Local Consistency Mechanisms.

2 Preliminaries

Model of Computation.

Accessing lookup tables with substrings.

2.1 Revisiting Restricted Recompression

Proposition 2.1 ([28, Propositions 3.4 and 4.7]).

▶ Remark 2.2.

Case 1: 𝒌 is even.

Case 2: 𝒌 is odd.

3 Restricted Recompression in Sublinear Time

Definition 3.1.

Corollary 3.2 (of [28, Proposition 4.7]).

Proof.

Corollary 3.3.

Proof.

3.1 Performing the Initial 𝑲 Rounds

Lemma 3.4.

Defining phrase boundaries via substrings.

Lemma 3.5.

Proof.

Initialization.

Preparing round 𝒌+𝟏.

Performing an even round.

Performing an odd round.

Time complexity and correctness.

3.2 Reporting the Phrase Boundaries

Lemma 3.6.

Proof.

Lemma 3.7.

Proof.

Lemma 3.8.

Proof.

Lemma 3.9.

Proof.

4 Computing 𝝉-Runs in Sublinear Time

Fact 4.1 ([29, Lemma 1(ii)]).

Theorem 4.2 ([28, Theorem 1.5]).

Proposition 4.3.

Proof.

Lemma 4.4.

Proof.

Proposition 4.5.

Proof.

5 String Synchronizing Sets in Sublinear Time

Definition 5.1 (Synchronizing set [22]).

Proposition 5.2 ([28, Construction 3.5 and Lemma 5.2]).

Theorem 5.3 (Compare [28, Theorem 1.13]).

Proof.

Theorem 5.4.

Proof.

6 Improving the Query Time

Lemma 6.1.

Proof.

Sparse encodings.

Definition 6.2 (Elias-γ code [14]).

Definition 6.3 (Sparse encoding).

Example 6.4.

Observation 6.5.

Observation 6.6.

Observation 6.7.

Parsing sparse encodings.

Lemma 6.8.

Lemma 6.9.

Time-Optimal Construction
of String Synchronizing Sets

$\blacktriangleright$ Remark 2.2.

Case 1: $𝒌$ is even.

Case 2: $𝒌$ is odd.

3.1 Performing the Initial $𝑲$ Rounds

Preparing round $k+1$ .

4 Computing $\tau$ -Runs in Sublinear Time

Definition 6.2 (Elias- $\gamma$ code [14]).

Running the transducer on $\mathsf{sp\smash{\underline{\phantom{o}}}enc}(S)$ .