## 3 Non-Overlapping LZSS
### Complexity Bounds
With the above analysis, we again obtain \(\mathcal{O}(nt_{\text{SA}})\) time for the algorithm computing the non-overlapping factorization (as well as the non-Type 3 LPnF values) by spending \(\mathcal{O}(t_{\text{SA}})\) time for each charged character (instead of each visited node). Let us reconsider that the factor of \(\text{LPnf}[i-1]\) is of Type 3, where we charge the last edge \((u,v)\) for computing \(\text{LPnf}[i-1]\) with \(\delta\) characters. Here, we observe that we actually spend only \(\mathcal{O}(t_{\text{SA}})\) time for processing this edge. Hence, we have \(\delta-1\) characters as a credit left, which we can spend on traversing \(\mathcal{O}(\delta)\) descendants of \(\bar{u}\). If the factor starting at \(i\) is again of Type 3, we add the remaining credit to the newly gained credit, and recurse. Regarding Section 3.3 (b), computing the length of the LCP of \(T[j_{0}\,..]\) and \(T[\text{sufnum}(\lambda)\,..]\) naively results again in \(\mathcal{O}(n^{2})\) overall running time since we need to compute these lengths for all \(n\) positions. Here, instead of computing the length of such an LCP naively, we determine it by computing \(\text{str\_depth}(w)\) of the LCA of \(\lambda\) and the leaf \(\lambda^{\prime}\) with suffix number \(j_{v}\) in \(\mathcal{O}(t_{\text{SA}})\) time. We find \(\lambda^{\prime}\) with the RMQ data structure on SA that actually reports the leaf-rank instead of the suffix number \(j_{v}\), which we obtain by accessing SA. Altogether, we obtain the same time and space bounds for computing the non-overlapping LZSS factorization:

Theorem 3.3: _We can compute the \(2n\)-bits representation of \(\text{LPnf}\) within the same time and space as the non-overlapping LZSS factorization described in Theorem 3.1._

Figure 5: Computing \(\text{LPnf}[i]\) from \(\text{LPnf}[i-1]\) by simulating a suffix link from \(u\) to \(\bar{u}\) (cf. Section 3.5). Straight arcs symbolize edges, while curly arcs symbolize paths visiting multiple nodes (which are not visualized). We have \(\text{str\_depth}(u)+\delta=\text{LPnf}[i-1]\), and hence \(\text{str\_depth}(\bar{u})+\delta=\text{LPnf}[i-1]-1\). We have \(\delta>0\) if and only if the factor starting at text position \(i-1\) is of Type 3. In that case, we additionally walk down from \(\bar{u}\) towards \(\bar{\lambda}\) to find the lowest node \(\bar{v}\) with \(\text{str\_depth}(\bar{v})\leq\text{LPnf}[i-1]-1=\text{str\_depth}(u)+\delta-1\). While \(u\) and \(v\) are directly connected with an edge, the path from \(\bar{u}\) to \(\bar{v}\) may contain multiple edges. ## 4 Substring Compression Query Problem

The substring compression query problem [6] is to find the compressed representation of \(T[\mathcal{I}]\), given a query interval \(\mathcal{I}\subset[1\mathinner{\ldotp\ldotp}n]\). [PERSON] and [PERSON] [6] solved this problem for LZSS with a data structure answering the query for \(\mathcal{I}\) in \(\mathcal{O}(z_{SS[\mathcal{I}]}\lg n\lg\lg n)\) time, where \(z_{SS[\mathcal{I}]}\) denotes the number of produced LZSS factors of the queried substring \(T[\mathcal{I}]\). Their data structure uses \(\mathcal{O}(n\lg^{c}n)\) space, and it can be constructed in \(\mathcal{O}(n\lg n)\) time. This result was improved by [PERSON] et al. [34] to \(\mathcal{O}(z_{SS[\mathcal{I}]}\lg n)\) query time for the same space or to \(\mathcal{O}(z_{SS[\mathcal{I}]}\lg^{c}n)\) query time for linear space. They also gave other trade-offs regarding query time and the size of the used data structure for larger data structures. The main idea of tackling the problem for LZSS (and similarly for the classic LZ77 factorization) is to use a data structure answering interval LCP queries, which are usually answered by two-dimensional range successor/predecessor data structures. Most recently, [PERSON] et al. [35] proposed a data structure answering an interval LCP query in \(\mathcal{O}(n^{c})\) time while taking \(\mathcal{O}(\epsilon^{-1}n(H_{0}(T)+1))\) bits of space, where \(H_{0}\) denotes the zeroth order empirical entropy.