## 2 Materials and Methods
### A Las Vegas Algorithm for \(K\) Mismatches
#### 2.4.2 The Randomized Algorithms of [17]  
Two different randomized algorithms are presented in [17] for solving the \(k\) mismatches problem. Both are Monte Carlo algorithms. In particular, they output the correct answers with high probability. The run times of these algorithms are \(O(nk\log m\log n)\) and \(O(n\log m(k+\log n\log\log n))\), respectively. In this section, we provide a summary of these algorithms. The first algorithm has \(O(k\log n)\) sampling phases, and in each phase, a 1 mismatch problem is solved. Each phase of sampling works as follows. We choose \(m/k\) positions of the pattern uniformly at random. The pattern \(P\) is replaced by a string \(P^{\prime}\) where \(|P^{\prime}|=m\), the characters in \(P^{\prime}\) in the randomly chosen positions are the same as those in the corresponding positions of \(P\), and the rest of the characters in \(P^{\prime}\) are set to wild cards. The 1 mismatch algorithm of Lemma 1 is run on \(T\) and \(P^{\prime}\). In each phase of random sampling, for each \(i\), we get to know if the Hamming distance between \(T_{i}\) and \(P^{\prime}\) is exactly 1, and, if so, identify the \(j\), such that \(t_{i+j-1}\
eq p_{j}^{\prime}\). As an example, consider the case when the Hamming distance between \(T_{i}\) and \(P\) is \(k\) (for some \(i\)). Then, in each phase of sampling, we would expect to identify exactly one of the positions (_i.e._, \(j\)) where \(T_{i}\) and \(P\) differ (_i.e._, \(t_{i+j-1}\
eq p_{j}\)). As a result, in an expected \(k\) phases of sampling, we will be able to identify all of the \(k\) positions in which \(T_{i}\) and \(P\) differ. It can be shown that if we make \(O(k\log n)\) sampling phases, then we can identify all of the \(k\) mismatches with high probability [17]. It is possible that the same \(j\) might be identified in multiple phases. However, we can easily keep track of this information to identify the unique \(j\) values found in all of the phases. Let the number of mismatches between \(T_{i}\) and \(P\) be \(q_{i}\) (for \(1\leq i\leq(n-m+1)\). If \(q_{i}\leq k\), the algorithm of [17] will compute \(q_{i}\) exactly. If \(q_{i}>k\), then the algorithm will report that the number of mismatches is \(>k\) (without estimating \(q_{i}\)), and this answer will be correct with high probability. The algorithm starts off by first computing \(E_{i}\) values for every \(T_{i}\). A list \(L(i)\) of all of the mismatches found for \(T_{i}\) is kept, for every \(i\). Whenever a mismatch is found between \(T_{i}\) and \(P\) (say in position \((i+j-1)\) of the text), the value of \(E_{i}\) is reduced by \(e_{i,j}\). If at any point in the algorithm, \(E_{i}\) becomes zero for any \(i\), this means that we have found all of the \(q_{i}\) mismatches between \(T_{i}\) and \(P\), and \(L(i)\) will have the positions in the text where these mismatches occur. Note that if the Hamming distance between \(T_{i}\) and \(P\) is much larger than \(k\) (for example, close or equal to \(m\)), then the probability that in a random sample we isolate a single mismatch is very low. Therefore, if the number of sample phases is only \(O(k\log n)\), the algorithm can only be Monte Carlo. Even if \(q_{i}\) is less or equal to \(k\), there is a small probability that we may not be able to find all of the \(q_{i}\) mismatches. Call this algorithm Algorithm 5. If for each \(i\), we either get all of the \(q_{i}\) mismatches (and hence, the corresponding \(E_{i}\) is zero) or we have found more than \(k\) mismatches between \(T_{i}\) and \(P\), then we can be sure that we have found all of the correct answers (and the algorithm will become Las Vegas). An example. Consider the example of \(\Sigma=\{1,2,3,4,5,6\},\ T=5\ 6\ 4\ 6\ 2\ *\ 3\ 3\ 4\ 5\ 1\ *\ 1\ 2\ 5\ 5\ 5\ 6\ 4\ 3\) and \(P=2\ 5\ 6\ 3\). Here, \(*\) represents the wild card. As has been computed before, \(E_{5}=162\) and \(E_{9}=182\). Let \(k=2\). In each phase, we choose 2 random positions of the pattern. In the first phase let the two positions chosen be 2 and 3. In this case, \(P^{\prime}=*\ 5\ 6\ *\).