## 3 Non-Overlapping LZSS
### Complexity Bounds
[4] used the fact that they can scan the leaves linearly in suffix number order to simulate the scan of the text in text order within their \(\mathcal{O}(n)\) time budget, we want to accelerate this algorithm by visiting only the leaves whose suffix numbers match the starting positions of the factors. With the SST, we can select the leaf \(\lambda\) with suffix number \(i\in[1\mathinner{. }n]\) in \(\mathcal{O}(1/\epsilon)\) time since we have access to \(\mathsf{ISA}[i]\) returning the leaf-rank of \(\lambda\). With the CST, we can visit the leaf with the subsequent suffix number with next_leaf in constant time, but may need \(\mathcal{O}(n)\) time to visit an arbitrary leaf. Here, the idea is to store a sampling of \(\mathsf{ISA}\) within \(\mathcal{O}(n\lg\sigma)\) bits of space during a precomputation step. We can produce the values of this sampling by iterating over next_leaf such that we obtain an array that stores in its \(i\)th entry the leaf-rank of the leaf with suffix number \(i\log_{\sigma}n\). Consequently, we can jump to a leaf with suffix number \(j\in[1\mathinner{. }n]\) in \(\mathcal{O}(\log_{\sigma}n)\) time by jumping to the closest sampled predecessor of \(j\), and subsequently applying next_leaf \(\mathcal{O}(\log_{\sigma}n)\) times to reach the leaf with suffix number \(j\). To sum up, we need \(\mathcal{O}(\log_{\sigma}n)\) time to traverse between two corresponding leaves. The total time becomes \(\mathcal{O}(\epsilon^{-1}z_{78[Z]}\lg z_{78[Z]})\) and \(\mathcal{O}(z_{78[Z]}(\lg z_{78[Z]}+\log_{\sigma}n))\) for the SST and the CST, respectively. ### LZ78 Coding

Finally, to obtain the LZ78 coding, we need to compute the referred indices. In a classic LZ78 trie, we would augment each trie node with the index of its corresponding factor. Here, we additionally need a trick for the implicitly represented LZ trie nodes: For them, we can now leverage the edge witnesses by augmenting each of them with the factor index of the currently lowest LZ trie node created on its ingoing edge. Fortunately, we know all nodes that become edge witnesses thanks to \(B_{E}\) (cf. Section 4.5) marking the preorder numbers of all edge witnesses. We now enhance \(B_{E}\) with a rank-support such that we can give each edge witness a rank within \([1\mathinner{.}z_{78[Z]}]\). Therefore, we can maintain the most recent factor indices corresponding to each edge witness in an array \(W\) of \(z_{78[Z]}\lg z_{78[Z]}\) bits. We again conduct a pass as described in Section 4.4, but this time we use \(W\) to write out the referred indices (see ([4] [Section 4.2.1 Pass (b)]) for a detailed description on how to read the referred indices from \(W\)). By doing so, we finally obtain Theorem 2. For an overview, we present the obtained complexity bounds in Table 1.

### Centroid-Path Decomposed Suffix Tree

If the length \(\ell\leq z_{78[Z]}\) of the longest factor is so large that \(\lg\ell=\omega(\lg\lg n)\), then we can speed up the exponential search of Section 4.5 by searching in the centroid-path decomposed suffix tree \(\mathsf{cpST}\). The centroid path decomposition [49] of the suffix tree is defined as follows: For each internal node, we call its child whose subtree is the largest among all its siblings (ties are broken arbitrarily if there are multiple such children) a _heavy_ node, while we call all other children _light_ nodes. Additionally, we make the root and all leaves light nodes (here we differ from the standard definition because we need a one-to-one relationship between leaves in the original tree and in the path-decomposed one). A _heavy path_ is a path from a light node \(u\) to the parent of a leaf containing, except for \(u\), only heavy nodes. There is a one-to-one relationship between light nodes and heavy paths. Since heavy paths do not overlap, we can contract all heavy paths to single nodes and thus form \(\mathsf{cpST}\) (see ([49] [Section 4.2]) for details and Figure 8 for an example).