The bitap algorithm (also known as the shift-or, shift-and or
Baeza-Yatesâ€“Gonnet algorithm) is an approximate string matching algorithm.
The algorithm tells whether a given text contains a substring which is
"approximately equal" to a given pattern, where approximate equality is
defined in terms of Levenshtein distance â€“ if the substring and pattern are
within a given distance k of each other, then the algorithm considers them
equal. The algorithm begins by precomputing a set of bitmasks containing
one bit for each element of the pattern. Then it is able to do most of the
work with bitwise operations, which are extremely fast.