## 7 Practical Issues and Testing  
In this section we present the experimental performance of the algorithms we described in the previous sections. As a baseline we used efficient sequential bit-parallel algorithms (namely BPM, the bit-parallel DP matrix of [PERSON] [54], and EXP, the exact pattern partitioning by [PERSON] and [PERSON] [55]). We also used a classical uncompressed hybrid index [52]. The algorithms of Section 3. lead to implementations LZI (the basic one, described in Section 3.1.) and DLZI (the advanced one, described in Section 3.2. ), as well as FMIndex, described in Section 3.3.. These structures work over the LZ-Index and FM-Index implemented by [PERSON] [50], where the second structure is a larger and faster variant of the usual FM-index implementations. Recall that these are pure filtration indexes, using Lemma 1 with \(A=P\) and \(B=O\), as described in the beginning of Section 2.3.. The algorithm explained in Sections 4. and 5. is the prototype called ILZI and it is based on the same ILZI compressed index [28]. For this prototype we used a stricter backtracking than what was explained in previous sections. For each pattern substring \(P[y_{1},y_{2}]\) to be matched, we computed the maximum number of errors that could occur when matching it in the text, also depending on the position \(O[x_{1},x_{2}]\) where it would be matched, and maximizing over the possible areas of \(O\) where the search would be necessary. For example, the extremes of \(P\) can be matched with fewer errors than the middle. This process involves precomputing tables that depend on \(m\) and \(k\). We omit the technical details. Note that we could use the ILZI to implement the exact partitioning algorithms run over the LZI and DLZI, yet the ILZI allows for a much stronger search, and we found it more interesting to stress this fact in the experiments. We also implemented a prototype, BiFMI, to test the algorithm described in Section 6.. We replaced the FCST with a bidirectional FM-Index over one wavelet tree [21]. The wavelet tree is a data structure that allows one to compute LF in \(O(\log\sigma)\) time. It contains \(\sigma\) bitmaps which add up to \(n\log\sigma\) bits (that is, the same space of the original text), on which \(rank\) and \(select\) operations are carried out to compute LF and its inverse. We compress these bitmaps using a technique [56] that solves \(rank\)/\(select\) in constant time and, when applied in the context of an FM-index, achieves \(nH_{k}\) bits of space [57]. We reverse the search so that the most common search (forwards) is done using LF (where the FM-index is faster) instead of \(\psi\). Replacing a suffix tree (FCST) by a compressed suffix array (BiFMI) was possible because we did not use the SLink operation of the FCST. Note that, since the BiFMI prototype is an FM-Index, it could also have been used to implement the algorithm described in Section 3.3., instead of the FMIndex structure (The converse is not true, as that FMIndex is intrinsically non-bidirectional. The formula for the inverse of LF [53] requires an operation called _select_ that can be carried out efficiently on wavelet-tree-based FM-indexes, but not on this implementation). Yet, the result is in all cases inferior to the hybrid indexing on the BiFMI. On the other hand, the BiFMI cannot reach the speed of the FMIndex for unidirectional search even if using the same amount of space. Thus we found it more interesting to implement the exact partitioning method over the larger and faster FMIndex, to show a different tradeoff. We tested our algorithm, BiFMI, in _automatic_ mode, _i.e._ Lemma 9 is used until every \(k_{i}<1\). We did not implement the algorithm of [PERSON] _et al._[48]. Instead we used the bit-parallel NFA of [PERSON] _et al._[58] and recomputed the \(D\) table whenever it was necessary to change the computing direction. Note this requires \(O(m)\) time when we switch from right to left or vice versa, but after the change it will require only \(O(k)\) time for each new row.