# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 4 Computing \(\mathsf{LPnrF}\)
### Algorithm of [PERSON] et al. We can also run the algorithm of [PERSON] et al. (2014) ((Algorithm 2)) with our suffix tree representations to obtain the same space and time bounds as stated in Theorem 2. For that, let us explain this algorithm in suffix tree terminology: For each leaf \(\lambda\) with suffix number \(i\), the idea for computing \(\mathsf{LPnrF}[i]\) is to scan the leaves for the leaf \(\lambda^{\star}\) with \(2n-\text{s\sf{w}inimum}(\lambda^{\star})\) being the referred position, and hence the string depth of \(\text{\sf{lca}}(\lambda,\lambda^{\star})\) is \(\mathsf{LPnrF}[i]\). To compute \(\lambda^{\star}\), we approach \(\lambda\) from the left and from the right to find \(\lambda_{\text{L}}\) (resp. \(\lambda_{\text{R}}\)) having the deepest LCA with \(\lambda\) among all leaves to the left (resp. right) side of \(\lambda\) whose suffix numbers are greater than \(2n-i\). Then either \(\lambda_{\text{L}}\) or \(\lambda_{\text{R}}\) is \(\lambda^{\star}\). Let \(\ell_{\text{L}}[i]\leftarrow\text{str\_depth}(\text{\sf{lca}}(\lambda_{ \text{L}},\lambda))\) and \(\ell_{\text{R}}[i]\leftarrow\text{str\_depth}(\text{\sf{lca}}(\lambda_{ \text{R}},\lambda))\). Then \(\mathsf{LPnrF}[i]=\max(\ell_{\text{L}}[i],\ell_{\text{R}}[i])\), and the referred position is either \(2n-\text{s\sf{w}inimum}(\lambda_{\text{L}})\) or \(2n-\text{ssf{w}inimum}(\lambda_{\text{R}})\), depending on whose respective LCA has the deeper string depth. Note that the referred positions in this algorithm are not necessarily always the leftmost possible ones. Correctness. Let \(j\) be the referred position of the leaf \(\lambda\) with suffix number \(i\) such that \(R[i\,..]\) and \(R[2n-j\,..]\) have the LCP \(F\) of length \(\mathsf{LPnrF}[i]\). Due to Lemma 1, there is a suffix tree node \(w\) whose string label is \(F\). Consequently, \(\lambda\) and the leaf with suffix number \(2n-j\) are in the subtree rooted at \(w\). Now suppose that we have computed \(\lambda_{\text{L}}\) and \(\lambda_{\text{R}}\) according to the above described algorithm. On the one hand, let us first assume that \(\ell_{\text{R}}[i]>\mathsf{LPnrF}[i]\) (the case \(\ell_{\text{L}}[i]>\mathsf{LPnrF}[i]\) is treated symmetrically). By definition of \(\ell_{\text{R}}[i]\), there is a descendant \(w^{\prime}\) of \(w\) with the string depth \(\ell_{\text{R}}[i]\), and \(w^{\prime}\) has both \(\lambda_{\text{R}}\) and \(\lambda\) in its subtree. However, this means that \(R[i\,..]\) and \(R[\text{s\sf{w}inimum}(\lambda_{\text{R}})\,..]\) have a common prefix longer than \(\mathsf{LPnrF}[i]\), a contradiction to \(\mathsf{LPnrF}[i]\) storing the length of the longest such LCP. On the other hand, let us assume that \(\max(\ell_{\text{L}}[i],\ell_{\text{R}}[i])<\mathsf{LPnrF}[i]\). Then \(w\) is a descendant of the node \(w^{\prime}\) being the LCA of \(\lambda\) and \(\lambda_{\text{R}}\). Without loss of generality, let us stipulate that the leaf \(\lambda^{\star}\) with suffix number \(2n-j\) is to the right of \(\lambda\) (the other case to the left of \(\lambda\) works with \(\lambda_{\text{L}}\) by symmetry). Then \(\lambda^{\star}\) is to the left of \(\lambda_{\text{R}}\), i.e., \(\lambda^{\star}\) is between \(\lambda\) and \(\lambda_{\text{R}}\). Since \(j>2n-i\), this contradicts the selection of \(\lambda_{\text{R}}\) to be the closest leaf on the right hand side of \(\lambda\) with a suffix number larger than \(2n-i\). Finding the Starting Points. Finally, to find the starting points of \(\lambda_{\text{L}}\) and \(\lambda_{\text{R}}\) being initially the leaves with the maximal suffix number to the left and to the right of \(\lambda\), respectively, we use a data structure for answering. **maxwf_leaf\((j_{1},j_{2})\)**: returning the leaf with the maximum suffix number among all leaves whose leaf-ranks are in \([j_{1}\,..\,j_{2}]\). We can modify the data structure computing max_ssfnum in Section 3.3 to return the leaf-rank instead of the suffix number (the used data structure for max_ssfnum first  
Figure 7: Setting of Section 4.1.