# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 3 Reversed LZ Factorization
### Determining the Referred Position
The actions of Player 1 differ in that she no longer needs to compute \(B_{\text{L}}\) and \(B_{\text{W}}\): When Player 1 visits a phrase leaf \(\lambda\), she locates the lowest ancestor \(w\) of \(\lambda\) marked in \(B_{\text{V}}\), which has to be marked in \(B_{\text{W}}\), too (as a side note: storing the depth of the witness of each phrase leaf in a list, sorted by the suffix numbers of these leaves, helps us to directly jump to the respective witness in constant time. We can encode this list as a bit vector of length \(\mathcal{O}(n)\) by storing each depth in unary coding (cf. [22] ([Section 3.4])). Nevertheless, we can afford the root-to-witness traversals of Player 1 since we visit at most \(\sum_{x=1}^{z}|F_{x}|=n\) nodes in total.). With the rank-support on \(B_{\text{W}}\), we can compute \(w\)'s witness rank \(i\), and obtain the referred position of \(\lambda\) with \(W[i]\) (cf. Line 10 of Algorithm 2). We show the final state after the first pass in Figure 6, together with \(W\) computed in the second pass. Overall, the time complexity is \(\mathcal{O}(\epsilon^{-1}n)\) time when working with either the SST or the CST. We use \(o(n)\) additional bits of space for the rank-support of \(B_{\text{W}}\), but costly \(z_{\text{W}}\lg n\) bits for the array \(W\). However, we can bound \(z_{\text{W}}\) by \(\mathcal{O}(n\lg\sigma/\lg n)\) since \(z_{\text{W}}\) is the number of distinct reversed LZ factors, and by an enumeration argument [40] ([Thm. 2]), a text of length \(n\) can be partitioned into at most \(\mathcal{O}(n/\log_{\sigma}n)\) distinct factors. Hence, we can store \(W\) in \(z_{\text{W}}\lg n=\mathcal{O}(n\lg\sigma)\) bits of space. With that, we finally obtain the working space bound of \(\mathcal{O}(\epsilon^{-1}n\lg\sigma)\) bits for the CST solution as claimed in Theorem 1. ```
1\(\lambda^{\text{R}}\leftarrow\text{prev\_leaf}(\text{prev\_leaf}(\text{ smallest\_leaf}))\) and \(\lambda\leftarrow\text{smallest\_leaf}\)
2 clear \(B_{\text{V}}\) and set \(B_{\text{V}}[\text{root\ node}]\gets 1\)
3\(W\leftarrow\text{array of size }z\lg z\)
4 while\(\lambda\
eq\lambda^{\text{R}}\)do
5 if\(B_{\text{L}}[\text{swithum}(\lambda)]=1\)then\(\triangleright\) turn of Player 1
6\(d\gets 0\)
7 while\(B_{\text{V}}[\text{level\_anc}(\lambda,d+1)]=1\)do\(d\gets d+1\)
8\(w\leftarrow\text{level\_anc}(\lambda,d)\)
9 if\(w\) is the root then output fresh factor
10 else output referred position \(W[B_{\text{W}}.\text{rank}_{1}(w)]\)\(\triangleright\) invariant: \(B_{\text{W}}[w]=1\)
11\(\lambda\leftarrow\text{suffixlink}(\lambda)\)\(\triangleright\) end of Player 1's turn
12 foreach node \(v\) on the path from \(\lambda^{\text{R}}\) up to the root do\(\triangleright\) turn of Player 2
13 if\(B_{\text{V}}[v]=1\) then break\(\triangleright\) end turn on reaching an already marked node
14\(B_{\text{V}}[v]\gets 1\)
15 if\(B_{\text{W}}[v]=1\) then \(W[B_{\text{W}}.\text{rank}_{1}(v)]=2n-\text{swithum}(\lambda^{\text{R}})\)
16\(\lambda^{\text{R}}\leftarrow\text{prev\_leaf}(\lambda^{\text{R}})\)\(\triangleright\) end of Player 2's turn
```  
**Algorithm 2**Determining the referred positions in a second pass described in Section 3.3. Figure 6: State of our running example at termination of Algorithm 1. We have computed the bit vector \(B_{\text{L}}\) of length \(n=11\) storing a one at the entries \(1,2,3,5\), and \(8\), i.e., the suffix numbers of the phrase leaves, which are marked in green, and the bit vector \(B_{\text{W}}\) of length \(38\) (the maximum preorder number of an ST node) storing a one at the entries \(20,22\), and \(32\), i.e., the preorder numbers of the witnesses, which are colored red. During the second pass described in Section 3.3, we compute \(W\) storing the referred positions in the order of the witness ranks (left table).