## 2 Basics and Contribution Overview
### Approximate String Matching  
The _edit_ or _Levenshtein_ distance between two strings, \(ed(A,B)\), is the smallest number of edit operations that transform \(A\) into \(B\). Valid operations are insertions, deletions, and substitutions of characters. Assuming we have a text \(T\), the problem we are interested in solving in this paper is: Given a pattern \(P\) and an error limit \(k\), determine all the (starting or ending positions of) substrings \(O\) of \(T\) for which \(ed(P,O)\leq k\). We now review the most basic techniques related to this problem. As our running example consider that \(P=abcba\), \(k=2\) and \(T=abbba\). The only occurrence \(O\) in \(T\) is \(abbba\). Dynamic programming.There is a well-known dynamic programming (DP) algorithm that computes matrix \(D\), where \(D[i,j]=ed(A[..i-1],B[..j-1])\) is the edit distance between the prefixes \(A[..i-1]\) and \(B[..j-1]\) of \(A\) and \(B\). Figure 2 (middle) shows an example of matrix \(D\) for \(A=abccba\) and \(B=abbab\). By looking at cell \(D[6,6]=3\) we can conclude that \(ed(abccba,abbabb)=3\). Let the size of \(A\) and \(B\) be \(m\) and \(m^{\prime}\) respectively. This matrix can be computed, in \(O(mm^{\prime})\) time, by setting \(D[0,0]=0\) and  
\[D[i,j]=\min\left\{ \begin{array}{ll}D[i-1,j]+1&\mbox{if $i>0$}\\ D[i,j-1]+1&\mbox{if $j>0$}\\ D[i-1,j-1]+\delta_{A[i-1]=B[j-1]}&\mbox{if $i,j>0$}\end{array} \right.\quad where\]  
\(\delta_{x=y}\) is 0 if \(x=y\) and 1 otherwise. [PERSON] [47] noted that in order to find cells in \(D\) whose value is \(k\) there is no need to compute cells with a value larger than \(k\); those can be replaced by \(+\infty\). The remaining cells are referred to as _active cells_. With this method, extending the computation of \(ed(A,B)\) to \(ed(Ac,B)\) or \(ed(A,Bc)\) requires only \(O(k)\) time: All we need to compute is another row, which can contain at most \(2k+1\) entries that are \(\leq k\) (as \(D[i,j]\geq|i-j|\)). Figure 1: On top, suffix tree for \(cbdbddcbababa\$\). Some suffix links are shown (dashed arrows). On the bottom, suffix array of \(T\). One can regard the edit distance matrix as an **edit graph**: Each matrix position \((i,j)\) is a node, which is the source of three arrows towards \((i,j+1)\) (of weight 1), \((i+1,j)\) (of weight 1), and \((i+1,j+1)\) (of weight \(\delta_{A[i]=B[j]}\)). Hence \(ed(A,B)\) is the weight of the shortest path from \((0,0)\) to \((m,m^{\prime})\). Backtracking.A way of performing ASM over indexed text is as follows. Perform a depth-first search over the suffix tree of \(T\), processing one letter at a time, while simultaneously computing the \(D\) table for \(P\) and \(O^{\prime}\), where \(O^{\prime}\) is the path-label of the node we are visiting. This table can be used to control the search. When we reach a point \(O^{\prime}\) such that \(ed(P,O^{\prime})\leq k\), _i.e._\(D[|P|,|O^{\prime}|]\leq k\), \(O^{\prime}\) is reported as an occurrence. Usually we also report all the positions in \(T\) at which \(O^{\prime}\) occurs, which means traversing the whole sub-tree of \(O^{\prime}\) and reporting all its leaf positions. Otherwise if \(ed(P,O^{\prime})>k\) but there is at least one active cell in the last row, _i.e._\(D[i,|O^{\prime}|]\leq k\) for some \(i\), this means that \(ed(P[..i-1],O^{\prime})\leq k\) and therefore \(O^{\prime}\) can potentially be extended into an occurrence, thus the search is allowed to proceed. If, on the other hand, there are no active cells in the last row of \(D\), the search within the subtree of the current node can be abandoned. For example, by looking at Figure 2 we can conclude that the search should not proceed further after \(abbbab\) because there are no active cells in the last row of the table. Also, since all the other rows contain active cells, this point is indeed reached by the search. It helps to think of \(D\) as a stack of rows that is growing downwards.