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 12 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:
Paul E. Black, "brute force string search with mismatches", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/bruteForceStrSrchwMismatch.html