# Reversed Lempel-Ziv Factorization with Suffix Trees +
## 3 Reversed LZ Factorization
### Factorization Algorithm
#### 3.2.1 Overview  
We explain our factorization algorithm in terms of a cooperative game with two players (We use this notation only for didactic purposes; the terminology must not be confused with game theory. Here, the notion of player is basically a subroutine of the algorithm having private and shared variables. ), whose pseudo code we sketched in Algorithm 1. Player 1 and Player 2 are allowed to access the leaves with suffix numbers in the ranges \([1\,..\,n]\) and \([n\,..\,2n-1]\), respectively. Player 1 (resp. Player 2) starts at the leaf with the smallest (resp. largest) suffix number, and is allowed to access the leaf with the subsequently next (resp. previous) suffix number via suffixlink (resp. prev_leaf). Hence, Player 1 simulates a linear forward scan in the text \(T\), while Player 2 simulates a linear backward scan in \(T^{\mathsf{R}}\). Both players take turns at accessing leaves at the same pace. To be more precise, in the \(i\)-th turn, Player 1 processes the leaf with suffix number \(i\), whereas Player 2 processes the leaf with suffix number \(2n-i\). In one turn, a player accesses a leaf \(\lambda\) and maybe performs a traversal on the path connecting the root with \(\lambda\). For such a traversal, we use level ancestor queries to traverse each node on the path in constant time. Whenever Player 2 accesses the leaf with suffix number \(n\) (shared among both players), the game ends; at that time both players access the same leaf (cf. Line 6 in Algorithm 1). In the following, we call this game a pass (with the meaning that we pass all relevant text positions). Depending on the allowed working space, our algorithm consists of one or two passes (cf. Section 3.3). The goal of Player 2 is to keep track of all nodes she visits. Player 2 does this by maintaining a bit vector \(B_{\mathsf{V}}\) of length \(4n\) such that \(B_{\mathsf{V}}[v]\) stores whether a node \(v\) has already been visited by Player 2, where we represent a node \(v\) by its pre-order number when using it as an index of a bit vector. To keep things simple, we initially mark the root node in \(B_{\mathsf{V}}\) at the start of each pass. By doing so, after the \(i\)-th turn of Player 2 we can read any substring of \(T[1\,..\,i]^{\mathsf{R}}\) by a top-down traversal from the suffix tree root, only visiting nodes marked in \(B_{\mathsf{V}}\). This is because of the invariant that the set of nodes marked in \(B_{\mathsf{V}}\) is upper-closed, i.e., if a node \(v\) is marked in \(B_{\mathsf{V}}\), then all its ancestors are marked in \(B_{\mathsf{V}}\) as well. The goal of Player 1 is to find the phrase leaves and the witnesses. For that, she maintains two bit vectors \(B_{\mathsf{L}}\) and \(B_{\mathsf{W}}\) of length \(n\) and \(4n\), respectively, whose entries are marked similarly to \(B_{\mathsf{V}}\) by using the suffix numbers (\(\in[1\,..\,n]\)) of the leaves accessed by Player 1 and preorder numbers of the internal nodes. We initially mark smallest leaf in \(B_{\mathsf{L}}\) since text position 1 is always the starting position of the fresh factor \(F_{1}\). By doing so, after the \(i\)-th turn of Player 1 we know the ending positions of those factors contained in \(T[1\,..\,i]\), which are marked in \(B_{\mathsf{L}}\). To sum up, after the \(i\)-th turn of both players we know the computed factors starting at text positions up to \(i\) thanks to Player 1, and can find the  
Figure 3: A reversed-LZ factor \(F\) starting at position \(i\) in \(R\) with a referred position \(j\geq|F|+1\). If \(\mathsf{a}=\bar{\mathsf{a}}\) with \(\mathsf{a},\bar{\mathsf{a}}\in\Sigma\), then we could extend \(F\) by one character, contradicting its definition to be the longest prefix of \(T[i\,..\,]\) whose reverse occurs in \(T[1\,..\,i-1]\). Hence, \(\mathsf{a}\
eq\bar{\mathsf{a}}\) and \(F\) is a right-maximal repeat. factor lengths thanks to Player 2, which we explain in detail in Section 3.2.2. There, we will show that the actions of Player 2 allow Player 1 to determine the starting position of the next factor.