## 3 Non-Overlapping LZSS  
Let \(z_{\text{ov}}\) and \(z\) denote the number of factors of the overlapping LZSS factorization (i.e., the standard LZSS factorization supporting overlaps) and of the non-overlapping LZSS factorization, respectively. [PERSON] and [PERSON] (2015) showed that \(z_{\text{ov}}\leq z\leq z_{\text{ov}}\cdot\mathcal{O}(\lg(n/(z_{\text{ov}} \log_{\text{v}}z_{\text{ov}})))\). Although being inferior to the overlapping LZSS factorization with respect to the number of factors, the non-overlapping LZSS factorization is an important tool for finding approximate repetitions ([PERSON] and [PERSON], 2015), periods ([PERSON] and [PERSON], 2015), seeds ([PERSON] and [PERSON], 2015), tandem repeats ([PERSON] and [PERSON], 2015), and other regular structures (cf. the non-overlapping s-factorization in (([PERSON] and [PERSON], 2015) [Chpt. 8])). Algorithms computing the non-overlapping LZSS factorization usually compute the longest previous non-overlapping factor table \(\mathsf{LPnf}[1\mathinner{. }n]\), where \(\mathsf{LPnf}[i]\) stores the length of the LCP of \(T[i\mathinner{. }]\) with all substrings \(T[j\mathinner{.}i\mathinner{. }-1]\) for \(j\in[1\mathinner{.}i\mathinner{. }i-1]\), which we set to zero if no such substring exists (i.e., \(\mathsf{LPnf}[1]=0\)). Having \(\mathsf{LPnf}\), we can iteratively compute the  
Figure 2: (**Left**) Suffix tree of the text \(T=\texttt{ababaaa$\$}\) with the witness nodes and the corresponding leaves of the non-overlapping LZSS factorization highlight in red () and in green (), respectively. We additionally mark the string ab with an implicit node (**�❝�**) whose string label is equal to the factor with Type 3. The nodes are labeled by their preorder numbers. The suffix number of each leaf \(\lambda\) is the underlined number drawn in dark yellow below \(\lambda\). (**Right**) Non-overlapping LZSS factorization of \(T\). non-overlapping LZSS factorization because \(F_{x}=T[k_{x}\ldots k_{x}+\max(0,\mathsf{LPnF}[k_{x}]-1)]\) with \(k_{x}:=\sum_{y=1}^{x-1}\lvert F_{y}\rvert+1\) for \(x\in[1\ldots z]\). We are aware of the algorithms of [PERSON] and [PERSON] [5] and [PERSON] et al. [21] computing \(\mathsf{LPnF}\) in linear time with a linear number of words. There are further practical optimizations [22; 23; 24] computing \(\mathsf{LPnF}\) in linear time for constant alphabets. Finally, [PERSON] and [PERSON] [25] gave a linear time conversion algorithm from the longest previous factor table \(\mathsf{LPF}\)[26] to \(\mathsf{LPnF}\) if the leftmost possible referred positions \(P[1\ldots n]\) with \(T[P[i]\ldots P[i]+\mathsf{LPF}[i]-1]=T[i\ldots i+\mathsf{LPF}[i]-1]\) for each text position \(i\in[1\ldots n]\) are provided. It seems possible that, instead of overwriting the \(\mathsf{LPF}\) array with the \(\mathsf{LPnF}\) array, we could run their algorithm on a \(2n\)-bits succinct representation of the \(\mathsf{LPF}\) array supporting sequential scan in constant time ([27] [Corollary 5]) to produce an \(\mathsf{LPnF}\) array representation within the same space due to the following lemma:  
Lemma 1: \(\mathsf{LPnF}[j-1]-1\leq\mathsf{LPnF}[j]\leq n-j\) _for \(j\in[2\ldots n]\)._  
Proof: Assume that \(\mathsf{LPnF}[j-1]>0\) (since \(\mathsf{LPnF}[j]\geq 0\) trivially holds). According to the definition, there exists an occurrence \(T[i\ldots i+\mathsf{LPnF}[j-1]-1]\) of \(T[j-1\ldots j-1+\mathsf{LPnF}[j-1]-1]\) with \(i+\mathsf{LPnF}[j-1]-1<j-1\). Hence, \(T[i+1\ldots i+\mathsf{LPnF}[j-1]-1]=T[j\ldots j+\mathsf{LPnF}[j-1]-2]\) and \(\lvert T[j\ldots j+\mathsf{LPnF}[j-1]-2]\rvert=\mathsf{LPnF}[j-1]-1\). Thus, \(T[j\ldots]\) has a common prefix with a substring of \(T[1\ldots j-1]\) of (at least) length \(\mathsf{LPnF}[j-1]-1\), i.e., \(\mathsf{LPnF}[j-1]-1\leq\mathsf{LPnF}[j]\). The upper bound follows from the fact that a factor cannot protrude \(T\) to the right. Consequently, \(\mathsf{LPnF}[1]+1,\mathsf{LPnF}[2]+2,\ldots,\mathsf{LPnF}[n]+n\) is non-decreasing.