## 3 Non-Overlapping LZSS
### The Factorization Algorithm
Here, we assign \(u\) and \(v\) the same roles as in Figure 3, but we additionally assume that \(j_{v}=j_{u}\) and \(\text{s\/\/num}(\lambda)\in\mathcal{I}\coloneqq[j_{u}+\text{str\_depth}(u) \dots j_{u}+\text{str\_depth}(v)-1]\). If \(\text{s\/\/num}(\lambda)=j_{u}+\text{str\_depth}(u)\), as in the right figure, then the factor \(F\) of \(\lambda\) starting at \(\text{s\/\/num}(\lambda)\) is of Type 2, and the witness of \(F\) is \(u\), although \(u\) is not the lowest ancestor of \(\lambda\) having \(\lambda\) and \(j_{u}\) in its subtree. If \(\text{s\/\
um}(\lambda)\in\mathcal{I}\setminus\{j_{u}+\text{str\_depth}(u)\}\), then \(F\) is of Type 3 and the witness of \(F\) is \(v\); the witness of \(F\) is \(v\) even if \(\lambda\) and the leaf with suffix number \(j_{v}\) are shared by a descendant of \(v\) as shown in the left figure. Figure 3: Determining the witness of a factor \(F\) whose starting position is the suffix number of the leaf \(\lambda\). Straight arcs symbolize edges, while curly arcs symbolize paths that can visit multiple nodes (which are not visualized). Given \(j_{w}\) is the smallest suffix number among all leaves in the subtree rooted at a node \(w\), and that \(u\) is the lowest ancestor of \(\lambda\) with \([j_{u}\dots j_{u}+\text{str\_depth}(u)-1]\cap[\text{s\/\/num}(\lambda)\dots \text{s\/\/num}(\lambda)+\text{str\_depth}(u)-1]=\emptyset\), then either \(u\) or its child \(v\) is the witness of \(F\) (see Section 3.2 for an explanation). The idea behind detecting whether the two intervals are intersecting is that a factor starting at \(\text{s\/\/num}(\lambda)\) of length \(\text{str\_depth}(u)\) would be of Type 1 or Type 2 with referred position \(j_{u}\). In fact, if \(F\) is of Type 1, then its witness is the lowest ancestor of \(\lambda\) having a leaf with a suffix number smaller than \(\text{s\/\/num}(\lambda)\) in its subtree (this definition coincides with the witnesses of the _overlapping_ LZSS factorization of ([4] [Section 2.3])). It is possible that \(j_{u}=j_{v}\), i.e., the leaf with suffix number \(j_{u}\) is also in the subtree rooted at \(v\). We can observe this case in Figure 4.  
* If \(j_{v}=\text{sfunum}(\lambda)\), there is no leaf in \(v\)'s subtree with a suffix number smaller than \(\text{sfunum}(\lambda)\). * If \(u\) is the root, then there is no candidate for a referred position available, i.e., \(F\) is a fresh factor (cf. Line 13 in Algorithm 1). * Otherwise, \(\text{str\_depth}(u)>0\) and \(\mathcal{I}_{u}\cap\mathcal{I}_{\lambda,u}=\emptyset\) (since \(v\) is the highest node on the path from the root to \(\lambda\) for which \(\mathcal{I}_{v}\cap\mathcal{I}_{\lambda,v}\
eq\emptyset\) holds). Hence, the longest substring occurring before \(\text{sfunum}(\lambda)\) that is a prefix of \(T[\text{sfunum}(\lambda)\,..]\) has an occurrence in \(T[1\,..\,\text{sfunum}(\lambda)-1]\) (Type 1). One of those occurrences starts at position \(j_{u}\). This means that the referred position is \(j_{u}\), and the witness of \(F\) is \(u\); the length of \(F\) is \(\text{str\_depth}(u)\) (cf. Line 17 in Algorithm 1). * If \(j_{v}\
eq\text{sfunum}(\lambda)\) (i.e., \(j_{v}<\text{sfunum}(\lambda)\)), the length of \(F\) is in the interval \([\text{str\_depth}(u)\,..\,\text{str\_depth}(v)-1]\). If the factor \(F\) refers to the position \(j_{v}\), then its length is the minimum of \(\text{sfunum}(\lambda)-j_{v}\) and the length of the LCP of the suffixes starting at \(j_{v}\) and \(\text{sfunum}(\lambda)\). (Note that this LCP can be longer than the string label of \(v\).) Let us denote the value of this minimum by \(\ell\), which coincides with \(\ell_{v}\) of Equation (1) due to \(\text{str\_depth}(v)\geq\text{sfunum}(\lambda)-j_{v}\), and determines whether \(F\) refers to \(j_{v}\) or \(j_{u}\) (cf. Line 20 in Algorithm 1):
* If \(\ell=\text{str\_depth}(u)\), then the referred position of \(F\) is actually the suffix number of a leaf contained in \(u\)'s subtree (Type 2).