Bitap Algorithm

Purpose: String matching using bit-parallelism. Exact matching in $O(nm/w)$ (effectively $O(n)$ when the pattern fits in a machine word), and — the reason it is famous — approximate matching with up to $k$ errors in $O(nkm/w)$. Also called shift-or, shift-and, or the Baeza-Yates-Gonnet algorithm.

Exact matching (shift-and form)

Precompute, for each character $c$, a mask $B[c]$ whose bit $j$ is 1 iff pattern[j] == c.

Maintain a state word $D$ where bit $j$ means “the first $j+1$ characters of the pattern match a suffix of the text read so far”. The update per text character is a single shift and AND:

$D\leftarrow ((D\ll 1)|1)\&B[t_i].$

A match ends at position $i$ exactly when bit $m-1$ of $D$ is set.

Code

// exact match, pattern length <= 64
vector<int> bitap(const string& text, const string& pat) {
    int m = pat.size();
    if (m == 0 || m > 64) return {};
    array<uint64_t, 256> B{};
    for (int j = 0; j < m; j++) B[(unsigned char)pat[j]] |= 1ULL << j;
 
    vector<int> hits;
    uint64_t D = 0, msb = 1ULL << (m - 1);
    for (int i = 0; i < (int)text.size(); i++) {
        D = ((D << 1) | 1ULL) & B[(unsigned char)text[i]];
        if (D & msb) hits.push_back(i - m + 1);
    }
    return hits;
}

Approximate matching (up to $k$ errors)

Keep $k+1$ state words $R_0,\dots ,R_k$, where $R_d$ tracks partial matches with at most $d$ edits. Per text character:

uint64_t old = R[0];
R[0] = ((R[0] << 1) | 1) & B[c];
for (int d = 1; d <= k; d++) {
    uint64_t tmp = R[d];
    R[d] = ((R[d] << 1 | 1) & B[c])   // match
         | ((old | R[d-1]) << 1 | 1)  // substitution / insertion
         |  R[d-1];                   // deletion
    old = tmp;
}

A match with $\le k$ errors ends at $i$ when the top bit of $R_k$ is set.

Paradigm

Bit-parallel simulation of a nondeterministic automaton. The state word is the set of active NFA states; the shift is the transition, the AND is the character filter. Doing 64 states at once is where the speed comes from.

Complexity

• Exact: $O(\lceil m/w\rceil \cdot n)$ time, $O(\sigma \lceil m/w\rceil )$ space
• Approximate: $O(k\lceil m/w\rceil \cdot n)$
• Preprocessing: $O(m+\sigma )$

When to use it

Situation	Best tool
Exact match, long pattern	KMP or Z
Exact match, pattern ≤ 64, huge text	Bitap — extremely cache-friendly
Approximate match, small $k$	Bitap
Approximate match, general	Full edit distance DP, or Myers’ bit-vector algorithm
Many patterns at once	Aho-Corasick

Variants / Use Cases

• Shift-or vs shift-and — identical up to complementing the masks; shift-or avoids the | 1 at the cost of inverted logic
• Myers’ bit-vector algorithm — computes full edit distance in $O(nm/w)$, strictly stronger than Bitap for large $k$
• agrep / TRE / fuzzy searches — Bitap is the engine behind fuzzy grep tools
• Wildcards and character classes — just set multiple bits in $B[c]$; no algorithmic change needed
• Bitset optimization — the general technique this exemplifies