  In this paper we consider several variants of the pattern matching problem.
In particular, we investigate the following problems: 1) Pattern matching with
k mismatches; 2) Approximate counting of mismatches; and 3) Pattern matching
with mismatches. The distance metric used is the Hamming distance. We present
some novel algorithms and techniques for solving these problems. Both
deterministic and randomized algorithms are offered. Variants of these problems
where there could be wild cards in either the text or the pattern or both are
considered. An experimental evaluation of these algorithms is also presented.
The source code is available at http://www.engr.uconn.edu/~man09004/kmis.zip.
