## 6 Hierarchical Approximate String Matching
### Indexed Hierarchical Verification
Instead of directly verifying the space around a \(B_{0}\) when \(ed(A_{i},B_{0})<k_{i}\) for a string \(B\) such that \(ed(A,B)<k\), we extend the error level gradually. Assuming \(i\) is even, this means checking for \(ed(A_{i}.A_{i+1},B_{1})<k_{i}+k_{i+1}\) first, for some \(B_{1}\). Figure 2 (right) shows an example of this process, computed with table \(D\). Whenever a row reaches a certain level in the hierarchy and contains active cells, the computation on that row is extended to activate the cells that are \(<k_{i}+k_{i+1}\). For example since \(D[2,2]=0\) the cells in row \(2\) that can be \(<1+\epsilon\) are activated, _i.e._ cells \(D[1,2]\) and \(D[3,2]\), that correspond to \(ed(a,ab)\) and \(ed(abc,ab)\). A similar process happens at row \(3\). In theory we can compute all the cells that have a value equal or smaller than \(k\) all the time. Still, we can also start to compute them at a given row, especially since it is not necessary to fill upwards the missing cells in the table. That is, we can compute the missing cells, up to \(k_{i}+k_{i+1}\), from the ones already in the table. There is no problem if the value of the new cells is larger than their value on the complete \(D\) table. In fact it is desirable. This will only make the algorithm skip occurrences that, because of Lemma 9, will be found in another case. To determine that \(ed(A_{i},B_{0})<k_{i}\) we must compute the \(D\) table for these two strings. Extending this computation to \(ed(A_{i}.A_{i+1},B_{1})<k_{i}+k_{i+1}\) is simple because table \(D\) only needs to be updated in its natural directions (to the right and downwards). From the suffix tree point of view this situation is also natural because it involves descending in the tree. Figure 7: A schematic representation of Lemma 9. When \(i\) is odd the situation is a bit trickier. This time we must check for \(ed(A_{i-1}.A_{i},B_{1})<k_{i-1}+k_{i}\). This is much more difficult because we need to move in the FCST by prepending letters to the current point. This is possible with the WeinerLink operation (recall Section 6.1.). Moreover we need to extend the DP in unnatural directions (to the left and upwards). For this we use the result [48] mentioned also in Section 6.1.. Hence computing each new row requires only \(O(k)\) operations. Note that the underlying operation on which their algorithm relies is the longest common prefix of any two suffixes of \(A\) and \(B\). To solve this we build a FCST for \(P\), in \(O(m)\) time, in uncompressed format so that the LCA operation takes \(O(1)\) time. Note that this FCST is built only once at the beginning of the algorithm and adds \(O(m\log m)\) bits to the space requirements of the algorithm. We determine the positions of \(O^{\prime}[i..]\) in that suffix tree, in \(O(m^{\prime})\) time, with the Parent and WeinerLink operations. Together with the LCA operation we can compute the size of the necessary longest common prefixes. Note that whenever \(O^{\prime}\) is extended to/contracted from \(cO^{\prime}\), this information must be updated, by recomputing in \(O(m^{\prime})\) time. Our algorithm consists in backtracking, where the error bound is gradually increased. Depending on the position of current \(P\)'s substring in the hierarchical verification, the string \(O^{\prime}\) is extended either to the left or to the right. Hence, as mentioned before, the \(ed(P,O^{\prime})\) states are stored in a stack, whereas the \(O^{\prime}\) string being generated is stored in a double stack structure that can be pushed/popped at both ends.