## 2 Preliminaries  
With \(\lg\) we denote the logarithm \(\log_{2}\) to base two. Our computational model is the word RAM model with machine word size \(\Omega(\lg n)\) for a given input size \(n\). Accessing a word costs \(\mathcal{O}(1)\) time. Let \(T\) be a text of length \(n\) whose characters are drawn from an integer alphabet \(\Sigma=[1\ldots\sigma]\) with \(\sigma=n^{\mathcal{O}(1)}\). Given \(X,Y,Z\in\Sigma^{*}\) with \(T=XYZ\), then \(X,Y\), and \(Z\) are called a _prefix_, _substring_, and _suffix_ of \(T\), respectively. We call \(T[i\ldots]\) the \(i\)th suffix of \(T\) and denote a substring \(T[i]\cdots T[j]\) with \(T[i\ldots j]\). Given a character \(\mathsf{c}\in\Sigma\) and an integer \(j\), the _rank_ query \(T\). \(\operatorname{rank_{\mathsf{c}}}(j)\) counts the occurrences of \(\mathsf{c}\) in \(T[1\ldots j]\) and the _select_ query \(T\). \(\operatorname{select_{\mathsf{c}}}(j)\) gives the position of the \(j\)th \(\mathsf{c}\) in \(T\). We stipulate that \(\operatorname{rank_{\mathsf{c}}}(0)=\operatorname{select_{\mathsf{c}}}(0)=0\). If the alphabet is binary, i.e., when \(T\) is a bit vector, there are data structures [7, 8] that use \(o(|T|)\) extra bits of space and can compute \(\operatorname{rank}\) and select  in constant time, respectively. Each of those data structures can be constructed in time linear in \(|T|\). We say that a bit vector has a _rank-support_ and a  
Figure 1: Juxtaposition of the overlapping LZSS factorization, the non-overlapping LZSS factorization, and the LZ78 factorization on the string \(T=\texttt{aaabaaaaba}\). A factor is visualized by a rounded rectangle. Its coding consists of a mere character if it has no reference; otherwise, its coding consists of its referred position and its lengths for both LZSS variants or its referred index and its last character for LZ78. select-support_ if it is endowed by data structures providing constant time access to rank and select, respectively. From now on, we assume that \(T\) ends with a special character \(\$\) smaller than all other characters appearing in \(T\). Under this assumption, there is no suffix of \(T\) having another suffix of \(T\) as a prefix. The _suffix trie_ of \(T\) is the trie of all suffixes of \(T\). There is a one-to-one relationship between the suffix trie leaves and the suffixes of \(T\). The _suffix tree_\(\mathsf{ST}\) of \(T\) is the tree obtained by compacting the suffix trie of \(T\). Similar to the suffix trie, the suffix tree has \(n\) leaves, but the number of internal nodes of the suffix tree is at most \(n\) because every \(\mathsf{ST}\) node is branching. The string stored in a suffix tree edge \(e\) is called the _label_ of \(e\). We define the function \(c(e)\) returning, for each edge \(e\), the length of \(e\)'s label. The _string label_ of a node \(v\) is defined as the concatenation of all edge labels on the path from the root to \(v\); its _string depth_, denoted by \(\mathsf{str\_depth}(v)\), is the length of its string label. The leaf corresponding to the \(i\)th suffix \(T[i\dots]\) is labeled with the _suffix number_\(i\in[1\dots n]\). We write \(\mathsf{sfnum}(\lambda)\) for the suffix number of a leaf \(\lambda\). The _leaf-rank_ is the preorder rank (\(\in[1\dots n]\)) of a leaf among the set of all \(\mathsf{ST}\) leaves, denoted by \(\mathsf{leaf\_rank}(\lambda)\) for a leaf \(\lambda\). For instance, the leftmost leaf in \(\mathsf{ST}\) has leaf-rank \(1\), while the rightmost leaf has leaf-rank \(n\). The function \(\mathsf{next\_leaf}(\lambda)\) returns the leaf whose suffix number is the suffix number of \(\lambda\) incremented by one, or \(1\) if the suffix number of \(\lambda\) is \(n\). Reading the suffix numbers stored in the leaves of \(\mathsf{ST}\) in leaf-rank order gives the suffix array [9]. We denote the suffix array and the inverse suffix array of \(T\) by \(\mathsf{SA}\) and \(\mathsf{ISA}\), respectively. The array \(\mathsf{ISA}\) is defined such that \(\mathsf{ISA}[\mathsf{SA}[i]]=i\) for every \(i=1,\dots,n\).