ShiftOr

Shift-Or is a bit-parallel algorithm for exact string matching in text. It is a variant of the Bitap family that uses binary bitmasks to track which prefixes of a pattern P of length m can end at the current position while scanning a text T.

In preprocessing, a bitmask S[c] is built for every character c in the alphabet. The masks encode which positions in the pattern can be continued by a given character. For each text character, the algorithm updates a small state vector D using fast bitwise operations (shifts and AND/OR with the masks). After processing a character, a full match of the pattern is detected when the bit corresponding to the last position of P indicates a complete alignment ending at the current text position.

The method is highly efficient when the pattern length m fits in the machine word (or a small number of words). If m fits in w bits, the state is contained in a single word, giving O(n) time for a text of length n and O(1) extra space per character. For longer patterns, the state spans multiple words, yielding O(n · ceil(m/w)) time and O(ceil(m/w)) space. The primary memory cost is the set of masks S[c] for the alphabet.

Variants of Shift-Or extend the approach to approximate matching, such as allowing a limited number of errors, by maintaining additional state vectors or adapting the recurrence. The algorithm can also be adapted for multiple patterns and remains a core example of bit-parallel string matching.

Applications include fast exact pattern search in text processing, DNA sequence analysis, and high-performance search tools. While especially effective for small alphabets and moderate pattern lengths, its efficiency diminishes for very large patterns or alphabets because of mask storage requirements.