# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 3 Reversed LZ Factorization
### Determining the Referred Position  
Up to now, we can determine the reversed-LZ factors \(F_{1}\cdots F_{z}=T\) with \(B_{\mathrm{L}}\) marking the starting position of each factor with a one. Yet, we have not the referred positions necessary for the coding of the factors (cf. Section 3.1). To obtain them, we have two options:  
Figure 5: Continuation of Figure 4 with the state at the fifth turn of Player 1. Additionally to the coloring used in Figure 4, witnesses are colored in red. In this figure, Player 1 just finished her turn on making the node with preorder number 32 the witness \(w\) of the leaf with suffix number 5. With \(w\) we know that the factor starting at text position 5 has the length \(\operatorname{str\_depth}(w)\) and that the next phrase leaf has suffix number 8. For visualization purposes, we left the hand () of Player 2 below the leaf of her last turn. The first option is easier but comes with the requirement for a support data structure on ST for the operation  
\[ \begin{array}{ll}\textbf{max\_swfnum}(v)&\text{returnuring the maximum among all suffix numbers of the leaves in the subtree rooted in $v$.}\\ \end{array} \]  
We can build such a support data structure in \(\mathcal{O}(\epsilon^{-1}n)\) time (resp. \(\mathcal{O}(\epsilon^{-1}n\log_{\sigma}^{\epsilon}n)\) time) using \(\mathcal{O}(n)\) bits to support max_swfnum in \(\mathcal{O}(\epsilon^{-1})\) time (resp. \(\mathcal{O}(\epsilon^{-1}\log_{\sigma}^{\epsilon}n)\) time) for the SST (resp. CST); see [22] ([Section 3.3]). Being able to query max_swfnum, we can directly compute the referred position of a factor \(F\) when discovering its witness \(w\) during a turn of Player 1 by max_swfnum\((w)\). max_swfnum\((w)\) gives us the suffix number of a leaf that has already been accessed by Player 2 since Player 2 accesses the leaves in descending order with respect to the suffix numbers, and \(w\) must have already been accessed by Player 2 during a leaf-to-root traversal (otherwise \(w\) would not have been marked in \(B_{\text{V}}\)). Since \(R[\text{max\_swfnum}(w)\ldots\text{max\_swfnum}(w)+\text{str\_depth}(w)-1]=F^{ \text{R}}\), the referred position of \(F\) is \(2n-\text{max\_swfnum}(w)\). Consequently, we can compute the coding of the factors during a single pass (cf. Line 17 of Algorithm 1), and are done when the pass finishes. The second option does not need to compute max_swfnum and retains the linear time bound when using CST. Here, the idea is to run an additional pass, whose pseudo code is given in Algorithm 2. For this additional pass, we do the following preparations: Let \(z_{\text{W}}\) be the number of witnesses, which is at most \(z\) since there can be multiple factors having the same witness. We keep \(B_{\text{L}}\) and \(B_{\text{W}}\) marking the phrase leaves and the witnesses, respectively. However, we clear \(B_{\text{V}}\) such that Player 2 has again the job to log her visited nodes in \(B_{\text{V}}\). We augment \(B_{\text{W}}\) with a rank-support such that we can enumerate the witnesses with ranks from 1 to at most \(z_{\text{W}}\), which we call the witness rank. We additionally create an array \(W\) of \(z_{\text{W}}\lg n\) bits. We want \(W[B_{\text{W}}.\text{rank}_{1}(w)]\) to store the referred position \(2n-\text{max\_swfnum}(w)\in[1\ldots n-1]\) for each witness \(w\) such that we can read the respective referred position from \(W\) when Player 1 accesses \(w\). We assign the task for maintaining \(W\) to Player 2. Player 2 can handle this task by taking additional action when visiting a witness (i.e., a node marked in \(B_{\text{W}}\)) during a leaf-to-root traversal: When visiting a witness node \(w\) with witness rank \(i\) from a leaf \(\lambda\), we write \(W[i]\gets 2n-\text{sfnum}(\lambda)\) if \(w\) is not yet marked in \(B_{\text{V}}\) (cf. Line 15 in Algorithm 2). Like before, Player 2 terminates her turn whenever she visits an already visited node.