## 5 Using a Lempel-Ziv Self-Index
### Homogeneous Lempel-Ziv Phrases  
In this section we give further insight into the structure of the homogeneous Lempel-Ziv phrases, _i.e._ those that verify the conditions of Lemma 4. The objective of this section is to analyze the complexity of the search for the escaping phrases, _i.e._ those that are not found in the \(q\)-grams based search. This search for these homogeneous phrases is described in point **(2)** of Section 5.2. We need a couple of lemmas that give further insight into the structure of these homogeneous phases. Lemma 4 explained that by restricting the minimal number of errors that a substring of \(A\), of size \(q\), may have we are also restricting the maximal number of errors that it can have. In fact this condition also restricts the spacing between consecutive errors. The next lemmas explain this property. **Lemma 6**: _Let A and B be strings and \(q\) and \(s\) be integers such that \(0\leq s\leq q\leq|A|\) and for any substrings \(B^{\prime}\) of \(B\) and \(A^{\prime}\) of \(A\) with \(|A^{\prime}|=q\) we have that \(ed(A^{\prime},B^{\prime})\geq s\). Then for any prefix of \(A^{\prime}\) of \(A\) such that for any substring \(B^{\prime}\) of \(B\), \(ed(A^{\prime},B^{\prime})\geq 1\) we can conclude that \(|A^{\prime}|>|A|-q\lceil(ed(A,B)-1+\epsilon)/s\rceil\), for any \(\epsilon>0\)._  
**Proof** Suppose by absurd that there is a prefix \(A^{\prime}\) of \(A\) such that for any substring \(B^{\prime}\) of \(B\) we have \(ed(A^{\prime},B^{\prime})\geq 1\) and \(|A^{\prime}|\leq|A|-q\lceil(ed(A,B)-1+\epsilon)/s\rceil\) for some \(\epsilon>0\). Now apply Lemma 2 with \(A_{1}=A^{\prime}\), \(|A_{j}|<q\) and the remaining \(A_{i}\)'s of size \(q\), _i.e._\(|A_{i}|=q\) and \(j=2+\lceil(ed(A,B)-1+\epsilon)/s\rceil\). Consider \(k_{1}=1\), \(k_{j}=0\) and the remaining \(k_{i}\)'s equal to \(s\). Therefore \(\sum_{i=1}^{j}k_{i}=1+s(j-2)=1+s\lceil(ed(A,B)-1+\epsilon)/s\rceil\geq 1+ed(A,B)-1+ \epsilon=ed(A,B)+\epsilon>ed(A,B)\). Therefore we conclude that there is a substring \(B^{\prime}\) of \(B\) and an \(i\) such that \(ed(A_{i},B^{\prime})<k_{i}\). This, however, is absurd because no value of \(i\) may verify this condition. Suppose that \(i=j\). Then \(ed(A_{j},B^{\prime})<k_{j}=0\), which is impossible. Suppose that \(1<i<j\). Then \(ed(A_{i},B^{\prime})<k_{i}=s\) with \(|A_{i}|=q\), which contradicts the hypotheses of the lemma. Finally, it cannot be that \(i=1\) either. That would mean that \(ed(A_{1},B^{\prime})=ed(A^{\prime},B^{\prime})<k_{1}=1\) for some \(B^{\prime}\) and this contradicts our initial hypotheses that \(ed(A^{\prime},B^{\prime})\geq 1\) for any \(B^{\prime}\). **Lemma 7**: _Let A and B be strings and \(q\) and \(s\) be integers such that \(0\leq s\leq q\leq|A|\) and for any substrings \(B^{\prime}\) of \(B\) and \(A^{\prime}\) of \(A\) with \(|A^{\prime}|=q\) we have that \(ed(A^{\prime},B^{\prime})\geq s\). Then for any prefix of \(A^{\prime}\) of \(A\) for which there is a substring \(B^{\prime}\) of \(B\), \(ed(A^{\prime},B^{\prime})\leq 1\) we can conclude that \(|A^{\prime}|<q\lceil(1+\epsilon)/s\rceil\), for any \(\epsilon>0\)._  
**Proof** Suppose by absurd that there is a prefix \(A^{\prime}\) of \(A\) for which there is a substring \(B^{\prime}\) of \(B\) such that \(ed(A^{\prime},B^{\prime})\leq 1\) and \(|A^{\prime}|\geq q\lceil(1+\epsilon)/s\rceil\), for some \(\epsilon>0\). Consider the suffix \(A^{\prime\prime}\) that results from \(A\) by removing \(A^{\prime}\). Consider also the suffix \(B^{\prime\prime}\) that results when removing \(B^{\prime}\) from \(B\). Note that \(B^{\prime}\) is not necessarily a prefix of \(B\), but we are only interested in the remaining suffix. We must have \(ed(A,B)\leq ed(A^{\prime},B^{\prime})+ed(A^{\prime\prime},B^{\prime\prime})\), because of the shortest path interpretation. Therefore \(ed(A^{\prime\prime},B^{\prime\prime})\geq ed(A,B)-ed(A^{\prime},B^{\prime}) \geq ed(A,B)-1\). The suffix \(A^{\prime\prime}\) however is too small to contain this number of errors.