brute force string search with mismatches

(algorithm)

Definition: Beginning with the (leftmost) position in a string and trying each position in turn, find the number of characters for which the pattern and the substring beginning at that position don't match (the Hamming distance). Return the first position with k or fewer mismatches.

Generalization (I am a kind of ...)
string matching with mismatches, brute force string search.

Author: PEB

Implementation

Gonnet and Baeza-Yates' (C and Pascal)

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 16 November 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "brute force string search with mismatches", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/bruteForceStrSrchwMismatch.html