## 3 Non-Overlapping LZSS
### Complexity Bounds
```
1\(\lambda\leftarrow\) leaf with suffix number 1\(\triangleright\) invariant: \(\lambda\) is always corresponding leaf repeat
2\(d\gets 1\)\(\triangleright\) depth counter for level_anc(\(\lambda,d\))
3\(\ell\gets 0\)\(\triangleright\) length of the factor corresponding to \(\lambda\)
4 while\(d\
eq\text{depth}(\lambda)\)do
5\(v\leftarrow\text{level\_anc}(\lambda,d)\)\(\triangleright\)\(j_{v}\) is the smallest suffix number of all leaves of \(v\)'s subtree
6\(j_{v}\leftarrow\mathsf{SA}[\mathsf{SA}.\mathsf{RMQ}[\text{leaf\_rank}( \text{most\_leaf}(v)),\text{leaf\_rank}(\text{most\_leaf}(v))]]\)\(\ell\leftarrow\text{str\_depth}(v)\)
7 if\([j_{v}\ldots\tilde{j_{v}}+\ell-1]\cap[\text{\sf{sufun}}(\lambda)\ldots\text{\sf{ sufun}}(\lambda)+\ell-1]=\emptyset\)then
8\(d\gets d+1\)continue\(\triangleright\) goto Line 5
9\(u\leftarrow\text{parent}(v)\)if\(j_{v}=\text{\sf{sufun}}(\lambda)\)then\(\triangleright\)\(\lambda\) has smallest suffix number in \(v\)'s subtree
10 if\(u\) is the root then\(\triangleright\)\(\lambda\) corresponds to a fresh factor
11\(\ell\gets 1\) and report fresh factor
12 break
13\(\ell\leftarrow\text{str\_depth}(u)\)\(\triangleright\) Type 1
14\(\text{report}(u,j_{u},\ell)\)\(\triangleright\)\(j_{u}\) has already been computed in the previous iteration
15 break
16\(\ell\leftarrow\min(\text{lcp}(T[j_{v}\ldots],T[\text{\sf{sufun}}(\lambda) \ldots]),\text{\sf{sufun}}(\lambda)-j_{v})\)if\(\ell\leq\text{str\_depth}(u)\)then\(\triangleright\) Type 2
17\(\ell\leftarrow\text{str\_depth}(u)\) and report\((u,j_{u},\ell)\)
18 else report\((v,j_{v},\ell)\)\(\triangleright\) Type 3
19 break
20\(\lambda\leftarrow\text{next\_leaf}^{(\ell)}(\lambda)\)\(\triangleright\) visit the next corresponding leaf
21 until\(\text{\sf{sufun}}(\lambda)=1\)

### Storing the Factorization

From here on, we have two options: We can either directly output the referred positions and the lengths of the computed factors during Pass (a), or we can store additional information for retrieving the witnesses in a later pass. Such a later pass is interesting when working with the SST, as we can store the factors in the \((1+e)n\lg n+\mathcal{O}(n)\) bits of working space ([4] [Section 3.3]). There, a later pass overwrites the space occupied by the SST, in particular the suffix array representation, such that later passes no longer can determine witnesses. Although we mark each witness in the bit vector \(B_{W}\) during Pass (a), there can be multiple nodes marked in \(B_{W}\) on the path from the root to a leaf corresponding to a factor \(F\). The overlapping LZSS factorization obeys the invariant that the witness of \(F\) is the lowest ancestor of \(\lambda\) that is marked in \(B_{V}\), given that \(B_{V}\) marks all ancestors of the leaves with



implicitly represented on the edge from \(u\coloneqq\text{parent}(v)\) to \(v\). We apply the same technique (i.e., taking the suffix link) as for the other types, but apply this technique on \(u\) instead of the witness \(v\), such that we end up at a node \(\bar{u}\) with \(\text{str\_depth}(\bar{u})=\text{str\_depth}(u)-1\). We sketch the setting in Figure 5. Now, we additionally need to walk down from \(\bar{u}\) towards \(\bar{\lambda}=\text{next\_leaf}(\lambda)\) to reach the lowest node \(\bar{v}\) with \(\text{str\_depth}(\bar{v})\leq\text{LPnf}[i-1]-1\). There can be at most \(c(u,v)\) nodes on the path from \(\bar{u}\) to \(\bar{v}\). We can refine this number to at most \(\delta\coloneqq\text{LPnf}[i-1]-\text{str\_depth}(u)\), where \(\delta\) is the number of characters on the edge \((u,v)\) contributing to \(\text{LPnf}[i-1]\). Nevertheless, these extra \(\delta\) nodes seem to invalidate the \(\mathcal{O}(n)\) bound on the number of visited nodes. To retain our claimed time complexity, we switch from counting nodes to counting characters and use the following charging argument: We charge each edge we traversed by \(c(e)\) characters, or \(\delta_{e}\) characters if we only traversed \(\delta_{e}\leq c(e)\) characters on an edge.