# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 4 Computing \(\mathsf{LPnrF}\)
### Algorithm of [PERSON] et al.
Having \(\lambda^{\prime}\), we consider:  
* If \(\text{leaf\_rank}(\lambda^{\prime})=\text{leaf\_rank}(\lambda)+1\) (meaning \(\lambda^{\prime}\) is to the right of \(\lambda\) and there is no leaf between \(\lambda\) and \(\lambda^{\prime}\)), we terminate. * Otherwise, we set \(\lambda^{\prime}_{\mathsf{R}}\) to the leaf with the largest suffix number among the leaves with leaf-ranks in the range \([\text{leaf\_rank}(\lambda)+1\ldots\text{leaf\_rank}(\lambda^{\prime})-1]\). If \(\text{sfnum}(\lambda^{\prime}_{\mathsf{R}})>2n-i\), we set \(\lambda_{\mathsf{R}}\leftarrow\lambda^{\prime}_{\mathsf{R}}\) and recurse. Otherwise we terminate. On termination, \(\ell_{\mathsf{R}}[i]=\text{str\_depth}(\text{lca}(\lambda_{\mathsf{R}},\lambda))\) because there is no leaf \(\lambda^{\prime\prime}\) on the right of \(\lambda\) closer to \(\lambda\) than \(\lambda_{\mathsf{R}}\) with \(\text{str\_depth}(\text{lca}(\lambda^{\prime\prime},\lambda))>\text{str\_ depth}(\text{lca}(\lambda_{\mathsf{R}},\lambda))\) and \(\text{sfnum}(\lambda^{\prime\prime})>2n-i\). Hence, \(\text{sfnum}(\lambda_{\mathsf{R}})\) is the referred position, and we continue with the computation of \(\ell_{\mathsf{R}}[i+1]\). See Figure 8 for a visualization. Figure 8: Computing \(\mathsf{LPnrF}\) with [14] ([Algorithm 2]) as explained in Section 4.2. Starting at the leaf \(\lambda_{\mathsf{R}}\), we jump to the leftmost leaf \(\lambda^{\prime}\) with \(\text{lca}(\lambda^{\prime},\lambda)=\text{lca}(\lambda_{\mathsf{R}},\lambda)\). Then, we use the operation \(\text{max\_sfnum}(\mathcal{I})\) returning the leaf-rank of the leaf \(\lambda^{\prime}_{\mathsf{R}}\) having the largest suffix number among the query interval \(\mathcal{I}=[\text{leaf\_rank}(\lambda)+1\ldots\text{leaf\_rank}(\lambda^{ \prime})-1]\). If \(\text{sfnum}(\lambda^{\prime}_{\mathsf{R}})>2n-i\), we recurse by setting \(\lambda_{\mathsf{R}}\leftarrow\lambda^{\prime}_{\mathsf{R}}\). The LCA of \(\lambda^{\prime}_{\mathsf{R}}\) and \(\lambda\) is at least as deep as the child \(v\) of \(u\) on the path towards \(\lambda\) (the figure shows the case that \(v=\text{lca}(\lambda^{\prime}_{\mathsf{R}},\lambda)\)), and hence \(\ell_{\mathsf{R}}[i]\) is at least \(\text{str\_depth}(v)\) if we recurse. Broadly speaking, the idea is that the closer \(\lambda_{\text{R}}\) gets to \(\lambda\), the deeper the string depth of \(\text{\rm{lca}}(\lambda_{\text{R}},\lambda)\) becomes. However, we have to stop when there is no closer leaf with a suffix number larger than \(2n-i\). So we first scan until reaching a \(\lambda^{\prime}\) having the same lowest common ancestor with \(\lambda\), and then search within the interval of leaves between \(\lambda\) and \(\lambda^{\prime}\) for the remaining leaf \(\lambda^{\prime}_{\text{R}}\) with the largest suffix number. We search for \(\lambda^{\prime}\) because we can jump from \(\lambda_{\text{R}}\) to \(\lambda^{\prime}\) with a range minimum query on the LCP array returning the index of the leftmost minimum in a given range. We can answer this query with an \(\mathcal{O}(n)\)-bits data structure in \(\mathcal{O}(e^{-1})\) or \(\mathcal{O}(e^{-1}\log_{e}^{e}n)\) time for the SST or the CST, respectively, and build it in \(\mathcal{O}(e^{-1}n)\) time or \(\mathcal{O}(e^{-1}n\log_{e}^{e}n)\) time (cf. (22) (Section 3.3)) and ([11]) ([11]) for details). However, with this algorithm, we may visit as many leaves as \(\sum_{i=1}^{n}2\ell_{\text{R}}[i]\leq\sum_{i=1}^{n}2\mathsf{LPnrf}[i]\) since each jump from \(\lambda_{\text{R}}\) to \(\lambda^{\prime}_{\text{R}}\) via \(\lambda^{\prime}\) brings us at least one value closer to \(\ell_{\text{R}}[i]\). To lower this bound to \(\mathcal{O}(n)\) leaf-visits, we again make use of Lemma 2 (cf. Section 4.1), but exchange \(\mathsf{LPnrf}[i]\) with \(\ell_{\text{R}}[i]\) (or respectively \(\ell_{\text{L}}[i]\)) in the statement of the lemma. Second Trick. Assume that we have computed \(\ell_{\text{R}}[i-1]=\text{\rm{lca}}(\lambda_{\text{R}},\lambda)\) with \(j\coloneqq\text{\rm{sfnum}}(\lambda_{\text{R}})>2n-i\).