# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 4 Computing \(\mathsf{LPnrF}\)
### Algorithm of [PERSON] et al.
Nodes marked in \(B_{\text{V}}\) are colored in blue. Curly arcs symbolize paths that can visit multiple nodes (which are not visualized). When visiting the lowest ancestor of \(\lambda\) marked in \(B_{\text{V}}\) for computing \(\mathsf{LPnrF}[i-1]\), Player 1 determines \(\bar{w}=\text{s\sf{wifixlink}}(w)\) such that she can skip the nodes on the path from the root to the leaf \(\tilde{\lambda}\) for computing \(\mathsf{LPnrF}[i]\) (these nodes are symbolized by the curly arc highlighted in yellow on the right). There are leaves \(\lambda^{\text{R}}\) and \(\tilde{\lambda}^{\text{R}}\) with suffix numbers of at least \(2n-i+2\) and \(2n-i+3\), respectively, since otherwise \(w\) would not have been marked in \(B_{\text{V}}\) by Player 2.  
computes the leaf-rank and then the respective suffix number). Finally, we need to take the border case into account that \(\lambda\) is the leftmost leaf or the rightmost leaf in the suffix tree, in which case we only need to approach \(\lambda\) from the right side or from the left side, respectively. The algorithm explained up to now already computes \(\mathsf{LPnrF}\) correctly, but visits \(\mathcal{O}(n)\) leaves per \(\mathsf{LPnrF}\) entry, or \(\mathcal{O}(n^{2})\) leaves in total. To improve this bound to \(\mathcal{O}(n)\) leaves, we apply two tricks. To ease the explanation of these tricks, let us focus on the right-hand side of \(\lambda\); the left-hand side is treated symmetrically. Overview for Algorithmic Improvements. Given we want to compute \(\ell_{\mathsf{R}}[i]\), we start with a pointer \(\lambda^{\prime}_{\mathsf{R}}\) to a leaf to the right of \(\lambda\) with suffix number larger than \(2n-i\), and approach \(\lambda\) with \(\lambda^{\prime}_{\mathsf{R}}\) from the right until there is no leaf closer to \(\lambda\) on its right side with a suffix number larger than \(2n-i\). Then \(\lambda^{\prime}_{\mathsf{R}}\) is \(\lambda_{\mathsf{R}}\), and we can compute \(\ell_{\mathsf{R}}[i]\) being the string depth of the LCA of \(\lambda_{\mathsf{R}}\) and \(\lambda\). If we scan linearly the suffix tree leaves to reach \(\lambda_{\mathsf{R}}\) with the pointer \(\lambda^{\prime}_{\mathsf{R}}\), this gives us \(\mathcal{O}(n)\) leaves to process. Now the first trick lets us reduce the number of these leaves up to \(2\ell_{\mathsf{R}}[i]\) many for computing \(\ell_{\mathsf{R}}[i]\). The broad idea is that with the max_sfinum operation we can find a leaf closer to \(\lambda\) whose LCA is at least one string depth deeper than the LCA with the previously processed leaf. In total, the first trick helps us to compute \(\mathsf{LPnrF}\) by processing at most \(\sum_{i=1}^{n}\max(\ell_{\mathsf{L}}[i],\ell_{\mathsf{R}}[i])=\mathcal{O}(n^ {2})\) many leaves. In the second trick, we show that we can reuse the already computed neighboring leaves \(\lambda_{\mathsf{L}}\) and \(\lambda_{\mathsf{R}}\) by following their suffix links such we process at most \(2(\ell_{\mathsf{R}}[i+1]-\ell_{\mathsf{R}}[i]+1)\) many leaves (instead of \(2\ell_{\mathsf{R}}[i+1]\)) for computing \(\ell_{\mathsf{R}}[i+1]\). Finally, by a telescoping sum, we obtain a linear number of leaves to process. First Trick. The first trick is to jump over leaves whose respective suffixes all share the same longest common prefix with \(T[i\ldots]\). We start with \(\lambda_{\mathsf{R}}\leftarrow\text{max\_leaf}(\text{leaf\_rank}(\lambda)+1, 2n)\) being the leaf on the right-hand side of \(\lambda\) with the largest suffix number. As long as \(\text{sfnum}(\lambda_{\mathsf{R}})>2n-i\), we search the leftmost leaf \(\lambda^{\prime}\) between \(\lambda\) and \(\lambda_{\mathsf{R}}\) (to be more precise: \(\text{leaf\_rank}(\lambda^{\prime})\in[\text{leaf\_rank}(\lambda)+1\ldots \text{leaf\_rank}(\lambda_{\mathsf{R}})]\)) with \(\text{lca}(\lambda^{\prime},\lambda)=\text{lca}(\lambda_{\mathsf{R}},\lambda)\).