## 3 Representing Array _LCP_  
The following alternatives were considered to represent _LCP_:  
**Sad-Gon** Encodes [PERSON]'s [11]\(H\) bitmap in plain form, using the _rank/select_ implementation of [PERSON] [39], which takes \(0.1n\) bits on top of the \(2n\) used by \(H\) itself[PERSON] This implementation answers _rank_ in constant time and _select_ in \(O(\log n)\) time via binary search.  
**Sad-OS** Like the previous one, but using the _dense array_ implementation of [PERSON] and [PERSON] [38] for \(H\). This requires about the same space as the previous one and answers _select_ in time \(O(\log^{4}r/\log n)\).  
**FMN-RRR** Encodes \(H\) in compressed form as in [PERSON] _et al_. [18], that is, by encoding sparse bitmaps \(Z\) and \(O\). We use the compressed representation by [PERSON] _et al_[PERSON] [37] as implemented by [PERSON] [40]. This costs \(0.54n\) extra bits on top of the entropy of the two bitmaps, \(2r\log\frac{n}{r}+O(r)\). Operation _rank_ takes constant time and _select_ takes \(O(\log n)\) time.  
**FMN-OS** Like the previous one, but instead of [PERSON] _et al._'s technique, we use the _sparse array_ implementation by [PERSON] and [PERSON] [38]. This requires \(2r\log\frac{n}{r}+O(r)\) bits and solves _select_ in time \(O(\log^{4}r/\log n)\).  
**PT** Inspired in an LCP construction algorithm [41], we store a particular sampling of _LCP_ values, and compute the others using the sampled ones. Given a parameter \(v\), the sampling requires \(n+O(n/\sqrt{v}+v)\) bytes of space and computes any _LCP\([i]\)_ by comparing at most some \(T[j,j+v]\) and \(T[j^{\prime},j^{\prime}+v]\). As we must obtain these symbols using \(\Psi\) up to \(2v\) times, the idea is slow.  
**PhiSpare** This is inspired in another construction [42]. For a parameter \(q\), we store in text order an array _PLCP\({}_{q}\)_ with the _LCP_ values for all text positions \(q\cdot k\). Now assume \(A[i]=qk+b\), with \(0\leq b<k\). If \(b=0\), then _LCP\([i]=\)PLCP\({}_{q}[k]\)_. Otherwise, _LCP\([i]\)_ is computed by comparing at most \(q+\)PLCP\({}_{q}[k+1]-\)PLCP\({}_{q}[k]\) symbols of the suffixes \(T[A[i-1],n]\) and \(T[A[i],n]\). The space is \(n/q\) integers and the computation requires \(O(q)\) applications of \(\Psi\) on average.  
**DAC** The _directly addressable codes_ of [PERSON] _et al._[43]. Most _LCP_ values are small (\(O(\log_{\sigma}n)\) on average), and thus require few bits. Yet, some can be much larger. Thus we can fix a block length \(b\) and divide each number of \(\ell\) bits into \(\lceil\ell/b\rceil\) blocks of \(b\) bits. Each block is stored using \(b+1\) bits, the last one telling whether the number continues in the next block or finishes in the current one. Those blocks are then rearranged to allow for fast random access. There are two variants of this structure, both implemented by [PERSON]: One with fixed \(b\) (_DAC_), and another using different \(b\) values for the first, second, _etc_. blocks, so as to minimize the total space (_DAC-Var_). Note we represent _LCP_ and not _PLCP_, thus we do not need to compute \(A[i]\).  
**RP**_Re-Pair_ As mentioned, Re-Pair can be used to compress the differential _LCP_ array, _LCP\({}^{\prime}\)_[18]. To obtain _LCP\([i]\)_ we store sampled absolute _LCP_ values and decompress the nonterminals since the last sample.