## 3 Non-Overlapping LZSS
### Complexity Bounds
Therefore, they could implicitly answer a substring compression query in \(\mathcal{O}(z_{SS[\mathcal{I}]}n^{c})\) time within compressed space. Recently, [PERSON] et al. [36] proposed data structures storing the LZSS-compressed suffixes of \(T\) for answering a pattern matching query of an LZSS-compressed pattern \(P\) without decompressing \(P\). Their proposed data structures also seem to be capable of answering substring compression queries. As a warm up for the more-involving techniques for the LZ78 factorization below (cf. Section 4.5), we show that our techniques studied for the non-overlapping LZSS factorization in Section 3 can be adapted to the substring compression query problem under the restriction that the query interval starts at text position \(1\) (meaning that we query for prefixes instead of arbitrary substrings). Given an interval \(\mathcal{I}=[1\mathinner{\ldotp\ldotp}p]\) for a text position \(p\in[1\mathinner{\ldotp\ldotp}n]\), the algorithm of Theorem 3 achieves \(\mathcal{O}(pt_{\mathsf{SA}})\) time, where \(t_{\mathsf{SA}}\) is the time to access \(\mathsf{SA}\). We can improve the running time by replacing the linear scan on Line 10 of Algorithm 1 with an exponential search [37]: As long as the condition on Line 9 is true (the condition for walking downwards), we do not increment the depth \(d\) by one, but instead double \(d\). Now, when the condition on Line 9 becomes false, we may have overestimated the desired depth (we want the first \(d\) for which the condition on Line 9 becomes false). Thus, we need to additionally backtrack by performing a binary search on the interval \([d/2\mathinner{\ldotp\ldotp}d]\). If we perform this search for computing a factor of length \(\ell\), then we double \(d\) at most \(\lg\ell\) times, and visit \(\mathcal{O}(\lg\ell)\) depths during the binary search (see also Figure 6 for a visualization). In total, we obtain \(\mathcal{O}(z_{SS[1\mathinner{\ldotp\ldotp}]}t_{\mathsf{SA}}\lg\ell)\) time, where \(\ell\) is the length of the longest non-overlapping LZSS factor (here, \(z_{SS[1\mathinner{\ldotp\ldotp}]}\) denotes the number of computed _non-overlapping_ factors). Note that the result is not particularly interesting since we can just store the whole factorization of \(T[1\mathinner{\ldotp\ldotp}n]\), scan for the leftmost factor \(F_{x}\) that ends at \(p\) or after, trim \(F_{x}\)'s length to end at \(p\), and finally return \(F_{1},\cdots,F_{x}\), all in \(\mathcal{O}(z_{SS[1\mathinner{\ldotp\ldotp}]})\) time. To generalize this algorithm for an interval \(\mathcal{I}\) with \(\mathsf{b}(\mathcal{I})>1\), we need to change the definition of \(j_{v}\) for a node \(v\) in Section 3.2 to be the smallest suffix number of at least \(\mathsf{b}(\mathcal{I})\) among the leaves in the subtree rooted at \(v\). However, this additional complexity makes the approach selecting \(j_{v}\) with an RMQ on SA infeasible and leads us back to the interval LCP query problem. ### Related Substring Compression Query Problems

As far as the author is aware of, the substring compression query problem has only been studied for LZSS. However, [PERSON] [38] mentioned that it is also feasible to think about the substring compression query problem in context of straight-line programs (SLPs): Given an SLP of size \(g\) representing \(T\), we can construct an SLP of size \(\mathcal{O}(g)\) on \(T[\mathcal{I}]\) in \(\mathcal{O}(g)\) time. Actually, we can do better if the SLP is locally consistent. For that, we augment each non-terminal with the number of terminal symbols it expands to (after recursively expanding all non-terminals by their right hand sides). For a grammar such as HSP ([39] [Theorem 3.5]), we can compute the SLP variant of HSP (analogously to the SLP variant of ESP [40]) in \(\mathcal{O}(\lg|\mathcal{I}|\lg^{*}n)\) time, or ESP [41] in \(\mathcal{O}(\lg^{2}|\mathcal{I}|\lg^{*}n)\) time due to ([39] [Lemma 2.11]).