## 3 Non-Overlapping LZSS
### Complexity Bounds  
To determine the value of \(j_{v}\), we need to answer a _range minimum query_ (_RMQ_) on SA. Given an array \(A[1\,..\,n]\), an RMQ for an interval \(\mathcal{I}\subset[1\,..\,n]\) asks for the index of the minimum value in \(A[\mathcal{I}]\). To answer an RMQ, we can make use of the following data structure:  
**Lemma 2** ([32] [Thm 5.8]). : _Let \(A[1\,..\,n]\) be an integer array, where accessing an element \(A[i]\) takes \(t_{A}\) time for \(i\in[1\,..\,n]\). There exists a data structure of size \(2n+o(n)\) bits built on top of \(A\) that answers RMQs in constant time. It is constructed in \(\mathcal{O}(t_{A}n)\) time with \(o(n)\) additional bits of working space._  
According to Lemma 2, we can construct an RMQ data structure in \(\mathcal{O}(t_{\textsf{SA}}n)\) time using \(2n+o(n)\) bits of space, where \(t_{\textsf{SA}}\) is the time for accessing SA. We can access SA in \(\mathcal{O}(1/\epsilon)\) time and in \(\mathcal{O}(\lg^{c}n)\) time with the SST and CST, respectively, where the last time complexity is due to the following lemma:  
**Lemma 3** ([PERSON] and [PERSON] [11] [Section 3.2]). : _There is a data structure using \(\mathcal{O}(\epsilon^{-1}n)\) bits that can access SA in \(\mathcal{O}(\lg^{c}n)\) time, where \(\epsilon\in(0,1]\) is a selectable constant._  
As shown by ([PERSON] et al. [33] [Lemma 3]), the operation \(\text{str\_depth}(u)\) for a node \(u\) can be computed with SA, LCP, and an RMQ data structure on LCP because the leaf-ranks of the leftmost leaf \(\lambda_{\textsf{L}}\) and rightmost leaf \(\lambda_{\textsf{R}}\) in the subtree rooted \(u\) define the interval \([\text{leaf\_rank}(\lambda_{\textsf{L}})+1\,..\,\text{leaf\_rank}(\lambda_{ \textsf{R}})]\) in SA, and selecting the minimum value in LCP within this interval gives the length of the longest common prefix shared among all leaves in \(u\)'s subtree, which is \(\text{str\_depth}(u)\). However, we do not store LCP explicitly, but instead simulate an access of its \(j\)th entry for \(j\in[2\,..\,n]\) by \(\textsf{LCP}[j]=\textsf{PLCP}[\textsf{SA}[j]]\). Hence, we can access an entry of LCP in \(\mathcal{O}(t_{\textsf{SA}})\) time. Consequently, we can build the data structure of Lemma 2 on LCP in \(\mathcal{O}(t_{\textsf{SA}}n)\) time, which takes \(2n+o(n)\) bits of additional space. Equippedwith this data structure, we finally can evaluate str_depth in \(\mathcal{O}(t_{\mathsf{SA}})\) time. The total time bounds are composed as follows:  
1. Since the number of visited nodes is at most the factor length of a corresponding leaf \(\lambda\) during a root-to-leaf traversal to \(\lambda\), and \(\sum_{x=1}^{z}|F_{x}|=n\), we conclude that the RMQs take \(\mathcal{O}(nt_{\mathsf{SA}})\) time in total. 2. For each root-to-leaf traversal to a leaf corresponding to a factor \(F\), we stop at an edge \((u,v)\) and compute the length of the LCP of \(T[j_{v}\ldots]\) and \(T[\text{\sf{sufun}}(\lambda)\ldots]\) by naively comparing \(\mathcal{O}(|F|)\) characters. In total, the number of compared characters is \(\mathcal{O}(\sum_{x=1}^{z}|F_{x}|)=\mathcal{O}(n)\). Altogether, Pass (a) takes takes \(\mathcal{O}(nt_{\mathsf{SA}})\) time, since all applied tree navigational operations take constant time. With Lemma 3, we obtain the time and space complexities claimed in Theorem 1.