## 2 Basics and Contribution Overview
### Approximate String Matching
Note that it is a convenient coincidence that the difference between the \(D\) tables of \(ed(P,O^{\prime})\) and \(ed(P,O^{\prime}c)\) is only the last row. This means that we can move between these two tables simply by adding or removing a row. At each step the DFS algorithm either pushes a new element into the stack, _i.e._ moves from \(ed(P,O^{\prime})\) to \(ed(P,O^{\prime}c)\), or it removes a row from the stack, _i.e._ moves from \(ed(P,O^{\prime}c)\) to \(ed(P,O^{\prime})\). The problem with backtracking is that the number of nodes it visits is at least exponential in \(k\), and usually in \(m\). Nevertheless, this process will be a key ingredient in our algorithms. Figure 2: \(D\) table computation for strings \(abccba\) and \(abbbab\). Left: schematic representation of the alignment. Middle: computation of \(D\). The numbers in bold correspond to the alignment shown on the left, and to the shortest path. Right: computation with increasing error bound. Filtration and sampling.Filtration algorithms build on the following lemma, simplified from [4]. **Lemma 1**: _Let A and B be strings such that \(ed(A,B)\leq k\). Let \(A=A_{1}A_{2}\ldots A_{j}\), for any \(j\geq 1\). Then there is a substring \(B^{\prime}\) of B and an \(i\) such that \(ed(A_{i},B^{\prime})\leq\lfloor k/j\rfloor\)._  
Consider for example \(k=2\) and \(A=P=A_{1}.A_{2}.A_{3}\), \(A_{1}=ab\), \(A_{2}=cc\), \(A_{3}=ba\) and \(B=O=abbba\). Since \(ed(A,O)=2\) and \(j=3\), we can conclude that there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that \(ed(A_{i},B^{\prime})\leq\lfloor 2/3\rfloor=0\). In particular \(ed(A_{1},ab)=0\). In this case we also have that \(ed(A_{3},ba)=0\). Note from the example that, if \(j=k+1\), then the \(A_{i}\)'s can be matched within \(B\) with zero errors, that is, using exact matching. If we assume that \(A=P\) and \(B\) is contained in \(O\), we can partition \(P\) into \(j\) non-overlapping parts and search \(T\) for them. Thus we must be able to find any text substring with the index (exactly [16] or approximately [17, 18], depending on \(j\)). Thus we must use a suffix tree or array [18], or even a \(q\)-gram index if we never use pieces of \(P\) longer than \(q\)[16, 17] (a \(q\)-gram index collects all text substrings of length \(q\) and stores a list of the positions of each different such text substring). The contexts around the occurrences found are then examined (say, with dynamic programming) for full occurrences of \(P\). Alternatively, if we assume that \(B=P\) and \(A\) is contained in \(O\), then we can index each \(s\)-th text \(q\)-gram (for some \(s\geq q\)), to form a so-called \(q\)-samples index. The different text \(q\)-samples are stored into, say, a trie data structure. This trie is traversed to find \(q\)-samples that match within \(P\) with at most \(\lfloor k/j\rfloor\) errors. The contexts around those \(q\)-samples are then verified. This works as long as \(q\) and \(k\) are sufficiently small compared to \(m\). More precisely, any occurrence \(O\) of \(P\) is of length at least \(m-k\). Wherever an occurrence lies, it must contain at least \(j=\lfloor(m-k-q+1)/q\rfloor\) complete \(q\)-samples, and this defines \(s\). This the basis of an \"approximate \(q\)-samples\" index [19].