## 3 Non-Overlapping LZSS
### Complexity Bounds
The algorithm works as follows: Suppose that we have computed the factors \(F_{1}\cdots F_{x-1}\) and now want to compute \(F_{x}\). Since \(F_{x}\) is a prefix of the suffix \(T[p\ldots]\) with \(p=|F_{1}\cdots F_{x-1}|+1\), \(F_{x}\) is a prefix of the concatenation of edge labels on the path \(\pi\) from the root to the leaf with suffix number \(p\) in the suffix tree. The additional requirement that \(F_{x}\), excluding its last character, has to coincide with a preceding factor \(F_{y}\) means that \(F_{y}=F_{x}[1\ldots|F_{x}|-1]\) is the string label of the lowest LZ trie node on \(\pi\); this LZ trie node is represented either

* explicitly as an \(\mathsf{ST}\) node \(w\) being the lowest edge witness on \(\pi\); or
* implicitly by the exploration counter of \(w\). In either case, \(w\) is the edge witness of \(F_{y}\) and determines its length \(|F_{y}|=\text{str\_depth}(\text{parent}(w))+n_{w}\). We create an LZ trie node representing \(F_{x}\) as follows:

* If \(n_{w}\) is not full, we make \(w\) the edge witness of \(F_{x}\), and increment \(n_{w}\) by one. Figure 8: **(Left) The suffix tree of \(T\) superimposed by the LZ trie (cf. Figure 7) computed on \(T=\texttt{aaababaaab\$}\). Blue () colored \(\mathsf{ST}\) nodes represent the explicit LZ trie nodes, i.e., those nodes that are present in \(\mathsf{ST}\). Implicit LZ trie nodes are represented by the small rounded nodes (). The edge witnesses are the nodes with the preorder numbers 3, 5, 6, 12, and 16. (Right) cpST of \(T\) described in Section 4.8. The label of a node is the list of preorder numbers of the nodes in its respective heavy path. For instance, the heavy path from the root contains the nodes with the preorder numbers 1, 3, 5, and 6. **

Figure 9: Excerpt of the suffix tree depicting three edge witnesses. Implicit trie node are represented by small rounded nodes (), which are shaded if they are LZ trie nodes (). The explicit LZ trie nodes () and \(w\) are shaded in blue (). According to the figure, \(n_{v}=1\) and \(n_{w}=2\). In particular, the exploration counters of \(u\) and \(w\) are full. Otherwise (\(n_{w}\) is full), we make the child \(w^{\prime}\) of \(w\) on the path \(\pi\) the edge witness of \(F_{x}\), and set \(n_{w^{\prime}}\gets 1\). It is left to find \(w\), which we can by traversing \(\pi\) from the root until reaching an edge \(e=(u,v)\) whose exploration counter \(n_{v}\) is less than the length of its label \(c(e)\), where either \(u\) or \(v\) is \(w\). However, a linear scan of \(\pi\) for finding \(w\) would result in \(\mathcal{O}(z)\) time per factor. Here, the fringe marked ancestor queries come into the picture, which allow us to find a lowest edge witness in amortized constant time: by marking all edge witnesses, querying the lowest marked ancestor of the leaf with suffix number \(p\) yields either \(u\) or \(v\). This gives us \(\mathcal{O}(1)\) amortized time per LZ78 factor, and concludes the LZ78 factorization algorithm of [PERSON] et al. (2016) (Theorem 3). Finally, to obtain the LZ78 factorization of \(T[\mathsf{b}(\mathcal{I})\dots\mathsf{e}(\mathcal{I})]\) for a given interval \(\mathcal{I}\) with \(\mathcal{I}=[\mathsf{b}(\mathcal{I})\dots\mathsf{e}(\mathcal{I})]\), we do not start the computation at \(T[1\dots]\), but directly at \(T[\mathsf{b}(\mathcal{I})\dots]\), and terminate when a factor ends at \(T[\mathsf{e}(\mathcal{I})]\) or protrudes \(T[\mathcal{I}]\) to the right. In the latter case, we trim this factor. Hence, we can compute the factorization of \(T[\mathcal{I}]\) in \(\mathcal{O}(z_{78[\mathcal{I}]})\) time with \(\mathcal{O}(n\lg n)\) bits of space, in which we can store a pointer-based suffix tree on \(T\). ### Outline

In what follows, we want to study variants of this algorithm that use more lightweight data structures at the expense of additional running times.