Exact match
Encode pattern as bitmask per alphabet char. State bit i = 'suffix of text matches first i+1 chars'. Shift + OR/AND per input char.
Advertisement
k-error
k+1 bit vectors, one per error count. Approximate match with k errors in single pass. O(N·k/w) with w-bit words.
Advertisement
Bit-parallelism
64-bit machine → patterns of length ≤ 64 handled in single word. Very fast for short patterns.
Applications
agrep. Approximate matching in bioinformatics. Fast fuzzy search for short queries.