## 7 A Repetition-Aware CST
### Grammar-Compressing the LCP Array  
To solve the queries on top of the LCP array, we represent a part of it in grammar-compressed form. This will be redundant with our compressed representation of array \(H\), which was already explained. Following the idea in [PERSON] _et al._[18], we grammar-compress the differential LCP array, defined as _LCP\({}^{\prime}[i]=\)LCP\({}^{\prime}[i]-\)LCP\({}^{\prime}[i-1]\)_ if \(i>1\), and _LCP\({}^{\prime}[1]=\)LCP\({}^{\prime}[1]\)_. This differential LCP array contains now \(O(r)\) areas that are exact repetitions of others, and a Re-Pair-based compression of it yields \(|R|+|C|=O(r\log\frac{n}{r})\) words [18,35]. We note, however, that the compression achieved in this way is modest [35]: We guarantee \(O(r\log\frac{n}{r})\)_words_, whereas the RLCSA and PLCP representations require basically \(O(r\log\frac{n}{r})\)_bits_. Indeed, the poor performance of variant _RP_ in Section 3 shows that the idea should not be applied directly. To overcome this problem, we take advantage of the fact that this representation is redundant with \(H\). We _truncate_ the parsing tree of the grammar, and use it as a device to speed up computations that would otherwise require expensive accesses to _PLCP_ (_i.e._, to bitmap \(H\)). Let \(R\) and \(C\) be the results of compressing _LCP\({}^{\prime}\)_ with Re-Pair. Every nonterminal \(i\) of \(R\) expands to a substring \(S[1,t]\) of _LCP\({}^{\prime}\)_. No matter where \(S\) appears in _LCP\({}^{\prime}\)_ (indeed, it must appear more than once),we can store some values that are intrinsic to \(S\). Let us define a relative sequence of values associated to \(S\), as follows: \(S^{\prime}[0]=0\) and \(S^{\prime}[j]=S[j]+S^{\prime}[j-1]\). Then, we define the following variables associated to the nonterminal:  
* \(min_{i}=\min_{1\leq j\leq t}S^{\prime}[j]\) is the minimum value in \(S^{\prime}\). * \(lmin_{i}\) and \(rmin_{i}\) are the leftmost and rightmost positions \(j\) where \(S^{\prime}[j]=min_{i}\), respectively. * \(sum_{i}=S^{\prime}[t]=\sum_{1\leq j\leq t}S[j]\) is the sum of the values \(S[j]\). * \(cover_{i}=t\) is the number of values in \(S^{\prime}\). As most of these values are small, we encode them with DACs [43], which use less space for short numbers while providing fast access (\(rmin\) is stored as the difference with \(lmin\)). To reduce space, we prune the grammar by deleting the nonterminals \(i\) such that \(cover_{i}<t\), where \(t\) will be a space/time tradeoff parameter. However, \"short\" nonterminals that are mentioned in sequence \(C\) are not deleted. This ensures that we can skip \(\Omega(t)\) symbols of _LCP_ with a single access to the corresponding nonterminal in \(C\), except for the short nonterminals (and terminals) that are retained in \(C\). To speed up traversals on \(C\), we join together maximal consecutive subsequences of nonterminals and terminals in \(C\) that sum up a total \(cover<t\): We create a new nonterminal rule in \(R\) (for which we precompute the variables above) and replace it in \(C\), deleting those nonterminals that formed the new rule and do not appear anymore in \(C\). This will also guarantee that no more than \(O(t)\) accesses to _LCP_ are needed to solve queries. Note that we could have built a hierarchy of new nonterminals by recursively grouping \(t\) consecutive symbols of \(C\), achieving logarithmic operation times just as with tree \(T_{m}\)[29], but this turned out to be counterproductive in practice. Figure 9 gives an example. Figure 9: On the left, example of the Re-Pair compression of a sequence \(T=\textit{LCP}^{\prime}\). We show \(R\) in array form and also in tree form. On the right, our _RP-NPR_ construction over \(T\), pruning with \(t=4\). We show how deep can the symbols of \(C\) be expanded after the pruning. Finally, sampled pointers are stored to every \(c\)-th cell of \(C\).