# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 3 Reversed LZ Factorization
### Factorization Algorithm
#### 3.2.2 One-Pass Algorithm in Detail  
In detail, a pass works as follows: at the start, Player 1 and Player 2 select smallest leaf and \(\text{prev\_leaf}(\text{prev\_leaf}(\text{smallest.leaf}))\), i.e., the leaves with suffix numbers \(1\) and \(2n-1\), respectively. Now the players take action in alternating turns, starting with Player 1. Nevertheless, we first explain the actions of Player 2, since Player 2 acts independently of Player 1, while Player 1's actions depend on Player 2. Suppose that Player 2 is at a leaf \(\lambda^{\mathsf{R}}\) (cf. Line 20 of Algorithm 1). Player 2 traverses the path from \(\lambda^{\mathsf{R}}\) to the root upwards and marks all visited nodes in \(B_{\mathsf{V}}\) until arriving at a node \(v\) already marked in \(B_{\mathsf{V}}\) (such a node exists since we mark the root in \(B_{\mathsf{V}}\) at the beginning of a pass.). When reaching the marked node \(v\), we end the turn of Player 2, and move Player 2 to \(\text{prev\_leaf}(\lambda^{\mathsf{R}})\) at Line 23 (and terminate the whole pass in Line 6 when this leaf has suffix number \(n\)). The foreach loop (Line 20) of the algorithm can be more verbosely expressed with a loop iterating over all depth offsets \(d\) in increasing order while computing \(v\leftarrow\text{level\_anc}(\lambda^{\mathsf{R}},d)\) until either reaching the root or a node marked in \(B_{\mathsf{V}}\). Subsequently, the turn of Player 1 starts (cf. Line 7). We depict the state after the first turn of Player 2 in Figure 4.  
If Player 1 is at a non-phrase leaf \(\lambda\), we skip the turn of Player 1, move Player 1 to \(\text{suffixlink}(\lambda)\) at Line 19, and let Player 2 take action. Now suppose that Player 1 is at a phrase leaf \(\lambda\) corresponding to a factor \(F\). Then we traverse the path from the root to \(\lambda\) downwards to find the lowest ancestor \(w\) of \(\lambda\) marked in \(B_{\text{V}}\). If \(w\) is the root node, then \(F\) is a fresh factor (cf. Line 11), and we know that the next factor starts immediately after \(F\) (cf. Line 13). Consequently, the leaf \(\text{suffixlink}(\lambda)\) is a phrase leaf. Otherwise, \(w\) is the witness of \(\lambda\), and \(\text{str\_depth}(w)=|F|\) (cf. Line 14). Hence, \(\text{sfnum}(\lambda)+\text{str\_depth}(w)\) is the suffix number of the phrase leaf \(\tilde{\lambda}\) that Player 1 will subsequently access. We therefore mark \(w\) and \(\text{sfnum}(\tilde{\lambda})=\text{sfnum}(\lambda)+\text{str\_depth}(w)\) in \(B_{\text{W}}\) and in \(B_{\text{L}}\), respectively (cf. Lines 16 and 18). We depict the fifth turn of our running example in Figure 5, during which Player 1 marks a witness node. Finally, we end the turn of Player 1, move [PERSON] 1 to \(\text{suffixlink}(\lambda)\) at Line 19, and let Player 2 take action. Correctness. When Player 1 accesses the leaf \(\lambda\) with suffix number \(i\), Player 2 has processed all leaves with suffix numbers \([2n-i+1\dots 2n-1]\). Due to the leaf-to-root traversals of Player 2, each node marked in \(B_{\text{V}}\) has a leaf with a suffix number in \([2n-i+1\dots 2n-1]\) in its subtree. In particular, a node \(w\) is marked in \(B_{\text{V}}\) if and only if the string label of \(w\) is a substring of \(R[2n-i+1\dots 2n-1]\). Because \(R[2n-i+1\dots 2n-1]^{\text{R}}=T[1\dots i-1]\), the longest prefix of \(T[i\dots]\) having a reversed occurrence in \(T[1\dots i-1]\) is therefore one of the string labels of the nodes marked in \(B_{\text{V}}\). In particular, we search the longest string label among those nodes, which we obtain with the lowest ancestor of \(\lambda\) marked in \(B_{\text{V}}\). Figure 4: Suffix tree of \(T\#\cdot T^{\text{R}}\cdot\$\) used in Section 3.2, where \(T=\text{abbabbabb}\) is our running example. The nodes are labeled by their preorder numbers. The suffix number of each leaf \(\lambda\) is the underlined number drawn in dark yellow below \(\lambda\).