## 3 Non-Overlapping LZSS
### Setup  
Our idea is an adaptation of the LZSS factorization introduced in ([4] [Section 3]). To explain our approach, we first stipulate that \(T\) ends with a unique character \(\mathfrak{s}\) that is smaller than all other characters appearing in \(T\). Next, we distinguish between fresh and referencing factors. We say that a factor is _fresh_ if it is the leftmost occurrence of a character. We call all other factors _referencing_. A referencing factor \(F_{x}\) has a reference pointing to the starting position of its longest previous occurrence (as a tie break, we always select the _leftmost_ such position). We call this starting position the _referred position_ of \(F_{x}\). More precisely, the referred position of a factor \(F_{x}=T[i\ldots i+\ell-1]\) is the smallest text position \(j\) with \(j+\ell\leq i\) and \(T[j\ldots j+\ell-1]=T[i\ldots i+\ell-1]\). Compared to the overlapping LZSS factorization, we require here the additional restriction that \(j+\ell\leq i\). This makes the computation of the referred positions more technical: Let \(j\) be the referred position of a factor \(F\coloneqq T[i\ldots i+\ell-1]\), and let \(S\) be the longest substring starting before \(i\) that is a prefix of \(T[i\ldots]\). We associate the factor \(F\) with one of the following three types:* \(T[j\ldots j+\ell-1]=S\) (the factor \(F\) coincides with the overlapping LZSS factor that would start at \(T[i\ldots]\));
* \(T[j\ldots j+\ell-1]\) is shorter than \(S\), but \(T[j+\ell]\
eq T[i+\ell]\) (then there is a suffix tree node that has the string label \(F\)); or
* \(T[j+\ell]=T[i+\ell]\) and \(j+\ell=i\) (otherwise, the factor \(F\) could be extended to the right).  
An example is \(T=\mathsf{a}|\mathsf{b}|\mathsf{a}|\mathsf{b}|^{\frac{1}{2}}_{\mathsf{a}}| \mathsf{a}|^{\frac{1}{2}}_{\mathsf{a}}|\mathsf{\hat{s}}\), where the factor borders are symbolized by the vertical bar \(|\), and the referencing factors are labeled with their types (fresh factors are not labeled). If \(F\) is of Type 3, the suffixes \(T[j\ldots]\) and \(T[i\ldots]\) share more than \(\ell\) characters such that \(F\) is not a string label of any suffix tree node in general, but it is at least a prefix of the string label of a node. This is the case for the third factor \(\mathsf{ab}\) in the aforementioned example, as can be seen in Figure 2.  
To find the referred positions, we mark certain nodes as witnesses, which create a connection between corresponding leaves and their referred positions. A leaf is called _corresponding_ if its suffix number is the starting position of a factor. We say that the witness of a fresh factor is the root. For a referencing factor \(F\), the _witness_ of \(F\) is the highest node whose string label has \(F\) as a prefix; the witness of \(F\) determines the referred position of \(F\), which is the smallest suffix number among all leaves in its subtree.  
Despite this increased complexity compared to the overlapping LZSS factorization, the non-overlapping factorization can be computed with the suffix tree in \(\mathcal{O}(n\lg\sigma)\) time using \(\mathcal{O}(n\lg n)\) bits of space ([31][APL16]). Here, we adapt the algorithms of ([PERSON] et al. [4] [Section 3]) computing the overlapping LZSS factorization to compute the non-overlapping factorization by following the approach of [PERSON] [31]. Our goal is to compute the coding of the factors, i.e., the referred position and the length of each factor (cf. Figure 1).