Shift-Or Algorithm

Purpose: The complemented formulation of Bitap: exact string matching in $O(\lceil m/w\rceil n)$ using one shift and one OR per text character.

The Difference from Shift-And

Shift-and keeps a state word where bit $j$ = 1 means “prefix of length $j+1$ matches”. Shift-or stores the complement: bit $j$ = 0 means the prefix matches.

Precompute masks with the bits inverted: $B[c]$ has bit $j$ equal to 0 iff pattern[j] == c.

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

The shift brings in a 0 in the low bit for free — exactly the “start a new match attempt” semantics — so no | 1 is needed. A match ends at $i$ iff bit $m-1$ of $D$ is 0.

Code

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

Two machine instructions in the inner loop. On a modern CPU this saturates memory bandwidth on the text — it is hard to beat for short patterns.

Complexity

• Time: $O(\lceil m/w\rceil \cdot n)$, i.e. $O(n)$ for $m\le 64$
• Preprocessing: $O(m+\sigma )$
• Space: $O(\sigma \lceil m/w\rceil )$

Why It Works

The state word is a bitmask of the active states of the trivial NFA that recognises .*pattern. State $j$ is active after reading $t_1..t_i$ iff pattern[0..j] is a suffix of that prefix of the text. The transition “state $j$ becomes state $j+1$ if the character matches” is exactly a left shift followed by masking out positions where the character disagrees. Complementing turns the mask-out from an AND into an OR. ∎

Extending it for free

Because $B[c]$ is just “which pattern positions can this character occupy”, several features cost nothing:

Feature	How
Wildcard ?	clear bit $j$ in $B[c]$ for every $c$
Character class [abc]	clear bit $j$ in $B$ for a, b, c
Case-insensitive	clear the bit for both cases
Approximate ($k$ errors)	keep $k+1$ state words — see Bitap

Variants / Use Cases

• Bitap / shift-and — the same algorithm, uncomplemented, plus the approximate-matching extension
• Patterns longer than a word — chain several words with carry propagation; the constant grows but it stays linear
• KMP — the choice for long patterns where $m/w$ becomes large
• Aho-Corasick — for many patterns simultaneously
• Bitset optimization — the general “simulate an automaton 64 states at a time” technique