## 3 A Simple Self-Indexing Method
### Improving the Basic Solution  
In the sequel we introduce several improvements to the basic approach, to obtain what will be called _DLZI_ in the experiments.  
The basic approach carries out redundant work in occurrences of type 1. Assume we are looking for a piece \(P_{r}\) of \(P=A_{r}.P_{r}.B_{r}\), \(1\leq r\leq k+1\). Given an occurrence of it, we must extract text substring \(L_{r}\) of length \(|A_{r}|+k\) to the left, and \(R_{r}\) of length \(|B_{r}|+k\) to the right of the occurrence \(P_{r}\), for verification using DP. Consider a primary occurrence at LZ-trie node \(v=Z_{i}\). To extract the context, we will traverse the upward path from \(v\), so as to obtain the content of \(Z_{i}\). If necessary, we will locate (using other fast LZ-index structures) the node \(v_{-1}\) corresponding to \(Z_{i-1}\), \(v_{-2}\) for \(Z_{i-2}\), and so on, until we have extracted \(|L_{r}|\) characters. Now we locate \(v_{+1}\) to obtain \(Z_{i+1}\), and so on until extracting \(|R_{r}|\) characters to the right. Note that, towards the left, we can stop exactly when we have extracted \(|L_{r}|\) characters, as the phrases are obtained right-to-left, whereas towards the right we must extract complete phrases until exceeding \(|R_{r}|\), and then discard the unneeded characters from the last phrase.  
As explained, we have to repeat this process for each descendant of \(v\). Let \(u=Z_{j}\) be a child of \(v\) by character \(c\). The extraction of \(Z_{j}\) from \(u\) starts by obtaining \(c\) and then repeats exactly the process already carried out for \(v=Z_{i}\) (as \(Z_{j}=Z_{i}.c\)). Our aim is to factor out that redundant work.  
Given two strings \(S\) and \(X\), let us define the _suffix edit distance_ from \(S\) to \(X\) as  
\[sed(S,X) = \min_{j}\ ed(S,X[j..]),\]  
where we note that the formula is not symmetric. Similarly, we define the _prefix edit distance_  
\[ped(S,X) = \min_{j}\ ed(S,X[..j]).\]  
Note that \(sed(S,X)\) is easily computed by traversing \(X\) backwards, whereas \(ped(S,X)\) is easier if traversing \(X\) forwards. Now let \(P_{r}\) be a pattern piece found in the text, so that we have to verify the area \(L_{r}P_{r}R_{r}\) with DP. The occurrence \(O\) minimizing \(ed(P,O)\) may start anywhere in \(L_{r}\) and finish anywhere in \(R_{r}\). More precisely, there will be an occurrence within \(L_{r}P_{r}R_{r}\) iff  
\[sed(A_{r},L_{r})+ped(B_{r},R_{r})\leq k.\]We factor out the redundant work in the subtree of a primary occurrence \(v=Z_{i}\) as follows. First, we obtain \(Z_{i}\) and compute \(sed(A_{r},Z_{i})\), remembering the last row \(L_{row}\) of the DP matrix (where we have processed \(A_{r}\) and \(Z_{i}\) in reverse order, and assuming \(Z_{i}\) corresponds to the rows). Indeed, if \(|Z_{i}|\geq|L_{r}^{v}|\) (where \(L_{r}^{v}\) is the \(L_{r}\) text substring corresponding to occurrence \(v\)), we only process the last \(|L_{r}^{v}|\) characters of \(Z_{i}\). Otherwise, we obtain the nodes \(v_{-1}\), \(v_{-2}\), and so on until obtaining \(L_{r}^{v}\) and computing \(k^{\prime}=sed(A_{r},L_{r}^{v})\). If \(k^{\prime}>k\), there is no possible occurrence around \(v\). Otherwise, we obtain and process \(v_{+1}\), \(v_{+2}\), until either we obtain \(ped(B_{r},Z_{i+1}.Z_{i+2}\ldots)\leq k-k^{\prime}\) or we process more than \(|R_{r}^{v}|\) characters.  
Now we traverse the subtree of \(v\) while avoiding redundant work. We set up a new DP matrix between \(B_{r}\) and an initially empty string, and traverse the subtree while carrying out a process similar to that described in Section 2.2. so that, when we are at node \(u=Z_{j}\), the matrix corresponds to the edit distance computation between \(B_{r}\) and \(u\). Let \(R_{row}\) be the last row of this matrix upon reaching \(u\). Now we extract \(u_{-1}\), \(u_{-2}\), and so on, so as to compute \(k^{\prime}=sed(A_{r},L_{r}^{u})\) starting from \(L_{row}\), that is, we avoid reprocessing \(u\) itself. Then we extract \(u_{+1}\), \(u_{+2}\), and so on until finding \(\leq k-k^{\prime}\) errors or processing \(|R_{r}^{u}|\) characters.