## 3 Non-Overlapping LZSS
### Complexity Bounds
All LZ78 factorization algorithms here presented stick to the following general framework, which we call a _pass_: For each leaf \(\lambda\) whose suffix number is the starting position of a factor \(F\), locate the lowest edge witness \(w\) on the path from the root to \(\lambda\) and create a new LZ trie node by incrementing either \(n_{w}\) or the exploration counter of its child on the path towards \(\lambda\) as described in Section 4.3. Since \(w\) determines the length of the factor \(F\), we know the suffix number of the leaf that starts with the next factor. After a pass, we know the LZ trie topology due to the exploration counters. In a subsequent pass (Section 4.7), we use this knowledge to associate an edge witness \(w\) with the index of the most recent factor having \(w\) as its edge witness such that we can identify the referred indices with this association. However, before that, we reduce the space (Section 4.5) and subsequently show how to perform a pass within the reduced working space (Section 4.6). Finally, we accelerate a root-to-leaf traversal for long factors in Section 4.8. ### Space-Efficient Computation

In what follows, we give trade-offs for less space but slightly larger time bounds by using SST and CST. To get below \(\mathcal{O}(n\lg n)\) bits of space, we need to get rid of: (a) the \(\mathcal{O}(n\lg n)\)-bits marked ancestor data structure; and (b) the \(\mathcal{O}(n\lg n)\) bits for the exploration counters. For the latter (b), [PERSON] et al. (2016) (Section 4.1) presented a data structure representing the exploration counters within \(\mathcal{O}(n)\) bits on top of the suffix tree. For the former (a), we use level ancestor queries to simulate a fringe marked ancestor query: to this end, we mark all edge witnesses in a bit vector \(B_{E}\) of length \(2n\) such that \(B_{E}[j]=1\) if and only if the ST node with preorder rank \(j\) is an edge witness (remember that the number of nodes in ST is at most \(2n\)). Suppose now that we want to compute the factor \(F_{x}\). For that, we visit the leaf \(\lambda\) with suffix number \(\mathsf{b}(\mathcal{I})+|F_{1}\dots\dots F_{x-1}|\). As in Section 4.3, we want to find the lowest edge witness on the path from the root to \(\lambda\), which we find with a fringe marked ancestor query. Here, we answer this query by scanning the path from the root to \(\lambda\) until reaching the lowest marked node in \(B_{E}\). We can traverse linearly from the root to this node by querying \(d\mapsto\text{level\_anc}(\lambda,d)\) for each depth \(d\geq 0\). However, we then visit \(\mathcal{O}(|F_{x}|)\) nodes for computing the factor \(F_{x}\), or \(\mathcal{O}(|\mathcal{I}|)\) nodes in total. To improve this bound, we can apply again exponential search (cf. Figure 6). To see why that can be done, let \((v_{0},\dots,v_{m})\) be the path from the root \(v_{0}\) to \(\lambda=v_{m}\). If each node \(v_{d}\) (for each depth \(d\in[0\dots m]\)) is represented by its preorder number, then \(B_{E}[v_{0}]\dots B_{E}[v_{m}]=1^{k+1}0^{m-k}\) if the lowest edge witness has depth \(k\), which is the smallest \(k\leq|F_{x}|\) such that \(\text{str\_depth}(\text{level\_anc}(\lambda,k))\geq|F_{x}|-1\). Although we do not know \(k\) in advance, we can find the rightmost '1' in \(B_{E}[v_{0}]\dots B_{E}[v_{m}]\) with an exponential search visiting \(\mathcal{O}(\lg k)=\mathcal{O}(\lg|F_{x}|)\) nodes (we evaluate \(d\mapsto\text{level\_anc}(\lambda,d)\) for specific \(d\) and check each time whether the returned node is marked in \(B_{E}\)). Thus, we can determine \(|F_{x}|\) and \(F_{x}\)'s edge witness in \(\mathcal{O}(\lg|F_{x}|)\) time. Since \(|F_{x}|\leq x\), we spend \(\mathcal{O}(z_{78[Z]}\lg z_{78[Z]})\) time in total. ### Navigation in Small Space

To complete our algorithm for SST and CST, it is left to study how to access the leaves when issuing the level ancestor queries. While the LZ78 factorization algorithms of [PERSON] et al.