## 2 Preliminaries
The two arrays \(\mathsf{SA}\) and \(\mathsf{ISA}\) have the following relation with the two operations leaf_rank and sufnum on the \(\mathsf{ST}\) leaves:  
* For the \(\mathsf{ST}\) leaf \(\lambda\) with \(\mathsf{sfnum}(\lambda)=i\), we have \(\mathsf{leaf\_rank}(\lambda)=\mathsf{ISA}[i]\). * For the \(\mathsf{ST}\) leaf \(\lambda\) with \(\mathsf{leaf\_rank}(\lambda)=j\), we have \(\mathsf{sfnum}(\lambda)=\mathsf{SA}[j]\). * \(\mathsf{LCP}[1\dots n]\) is an array with \(\mathsf{LCP}[1]:=0\) and \(\mathsf{LCP}[j]\) being the length of the longest common prefix (LCP) of the _lexicographically_\(j\)th smallest suffix \(T[\mathsf{SA}[j]\dots]\) with its lexicographic predecessor \(T[\mathsf{SA}[j-1]\dots]\) for \(j\in[2\dots n]\). The permuted LCP array \(\mathsf{PLCP}\) ([10] [Section 4]) is a permutation of \(\mathsf{LCP}\) with \(\mathsf{PLCP}[i]\coloneqq\mathsf{LCP}[\mathsf{ISA}[i]]\) for \(i\in[1\dots n]\), and can be stored within \(2n+o(n)\) bits of space. The \(\Psi\)-function [11] is defined by \(\mathsf{SA}[i]=\mathsf{SA}[\Psi(i)]-1\) for \(i\in[1\dots n]\) with \(\mathsf{SA}[i]\
eq n\) (and \(\Psi(i)=\mathsf{ISA}[1]\) for \(\mathsf{SA}[i]=n\)). It can be stored in \(\mathcal{O}(n\lg\sigma)\) bits while supporting constant access time [12]. In this article, we focus on the following two suffix tree representations, which are an ensemble of some of the aforementioned data structures:  
* The succinct suffix tree (SST), using \((1+\epsilon)n\lg n+\mathcal{O}(n)\) bits of space ([4] [Section 2.2.3]) for a selectable constant \(\epsilon>0\), contains, among others, a \((1+\epsilon)n\lg n\)-bits representation of \(\mathsf{SA}\) and \(\mathsf{ISA}\) with \(\mathcal{O}(1/\epsilon)\) access time for each array. * The compressed suffix tree (CST) using \(\mathcal{O}(n\lg\sigma)\) bits of space [10,13] contains, among others, the \(\Psi\)-function. Both suffix tree representations can be constructed in linear time within their final space requirements (asymptotically) when neglecting the space requirements of the read-only text \(T\). They store the \(\mathsf{PLCP}\) array and a succinct representation of the suffix tree topology such as a balanced parentheses (BP) [7] sequence. The BP sequence represents a rooted, unlabeled but ordered tree of \(n\) nodes by a bit vector of length \(2n+o(n)\) bits. Since the suffix tree has at most \(2n\) nodes, the BP representation of the \(\mathsf{ST}\) topology uses at most \(4n+o(n)\) bits. For example, the BP sequence of the suffix tree given in Figure 2 is \(\langle\langle\langle\langle\langle\langle\langle\langle\langle\langle\langle\langle \langle\langle\langle\langle\langle\langle\all in constant time. Note that the _depth_ of a node \(v\), i.e., the number of edges from \(v\) to the root, is at most \(\text{str\_depth}(v)\). For our algorithms, we want to simulate a linear scan on the text from its beginning to its end by visiting the leaves in ascending order with respect to their suffix numbers (starting with the leaf with suffix number \(1\), and ending at the leaf with suffix number \(n\)). For that, we iteratively call next_leaf. We can compute next_leaf by first computing the leaf-rank of the succeeding leaf \(\text{next\_leaf}(\lambda)\) of a leaf \(\lambda\) with leaf_rank\((\text{next\_leaf}(\lambda))=\Psi[\text{leaf\_rank}(\lambda)]\), and then selecting next_leaf\((\lambda)\) by its leaf-rank; we can select a leaf by its leaf-rank in constant time due to the BP sequence representation of the suffix tree topology (the BP sequence can be augmented with a rank- and select-support for leaves represented by the empty parentheses '(')'. Since we can simulate \(\Psi\) with SA and ISA, the SST needs \(\mathcal{O}(1/\epsilon)\) time for evaluating next_leaf. Finally, a _factorization_ of \(T\) of size \(z\) partitions \(T\) into \(z\) substrings \(F_{1}\cdots F_{z}=T\). Each such substring \(F_{x}\) is called a _factor_.