# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 4 Computing \(\mathsf{LPnrF}\)
### Adaptation of the Single-Pass Algorithm  
Having an \(\mathcal{O}(n)\)-bits representation of \(\mathsf{LPnrF}\) gives us hope to find an algorithm computing \(\mathsf{LPnrF}\) in a total workspace space of \(o(n\lg n)\) bits. Indeed, we can adapt our algorithm devised for the reversed LZ factorization to compute \(\mathsf{LPnrF}\). For that, we just have to promote all leaves to phrase leaves such that the condition in Line 7 of Algorithm 1 is always true. Consequently, Player 1 performs a root-to-leaf traversal for finding the lowest node marked in \(B_{\mathsf{V}}\) of each leaf. By doing so, the time complexity becomes \(\mathcal{O}(n^{2})\), however, since we visit at most \(\sum_{i=1}^{n}\mathsf{LPnrF}[i]=\mathcal{O}(n^{2})\) many nodes during the root-to-leaf traversals (there are strings like \(T=\mathsf{a}\cdots\) a for which this sum becomes \(\mathcal{O}(n^{2})\)).  
To lower this time bound, we follow the same strategy as in [22] ([Section 3.5]) or [34] ([Lemma 6]) using suffixlink and Lemma 2: After Player 1 has computed \(\mathsf{str\_depth}(w)=\mathsf{LPnrF}[i-1]\) for \(w\) being the lowest ancestor marked in \(B_{\mathsf{V}}\) of the leaf with suffix number \(i-1\), we cache \(\tilde{w}\coloneqq\mathsf{suffixLink}(w)\) for the next turn of Player 1 such that Player 1 can start the root-to-leaf traversal to the leaf \(\tilde{\lambda}\) with suffix number \(i\) directly from \(\tilde{w}\) and thus skips the nodes from the root to \(\tilde{w}\). This works because \(\tilde{w}\) is the ancestor of \(\tilde{\lambda}\) with \(\mathsf{str\_depth}(\tilde{w})=\mathsf{LPnrF}[i-1]-1\), and \(\tilde{w}\) must have been marked in \(B_{\mathsf{V}}\) since \(\mathsf{LPnrF}[i]\geq\mathsf{str\_depth}(\tilde{w})\). See Figure 7 for a visualization. By skipping the nodes from the root to \(\tilde{w}\), we visit only \(\mathsf{LPnrF}[i]-\mathsf{LPnrF}[i-1]+1\) many nodes during the \(i\)-th turn of Player 1. A telescoping sum together with Lemma 2 shows that Player 1 visits \(\sum_{i=2}^{n}(\mathsf{LPnrF}[i]-\mathsf{LPnrF}[i-1]+1)=\mathcal{O}(n)\) nodes in total.  
The final bottleneck for CST are the \(n\) evaluations of \(\mathsf{str\_depth}(w)\) to compute the actual values of \(\mathsf{LPnrF}\) (cf. Line 15 of Algorithm 1). Here, we use a support data structure on CST for \(\mathsf{str\_depth}\)[34] ([Lemma 6]), which can be constructed in \(\mathcal{O}(\epsilon^{-1}n\log_{\sigma}^{\epsilon}n)\) time, uses \(\mathcal{O}(n)\) bits of space, and answers \(\mathsf{str\_depth}\) in \(\mathcal{O}(\epsilon^{-1}\log_{\sigma}^{\epsilon}n)\) time. This finally gives Theorem 2.  
\begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline \(i\) & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** \\ \hline \(T\)\# & a & b & b & a & b & b & a & b & a & b & \# \\ \(\mathsf{LPnrF}\) & 0 & 0 & 2 & 1 & 3 & 3 & 2 & 3 & 2 & 1 & 0 \\ \(\mathsf{LPnrF}\) & 0 & 0 & 1 & 3 & 3 & 3 & 2 & 3 & 2 & 1 & 0 \\ \(\mathsf{LPnrF}\) & 0 & 6 & 5 & 5 & 4 & 3 & 2 & 3 & 2 & 1 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 4: \(\mathsf{LPnrF}\) and \(\mathsf{LPnrF}\) of our running example. Both arrays are defined in Section 4. See Section 5 for the definition of \(\mathsf{LPnrF}\).