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
The method is highly efficient when the pattern length m fits in the machine word (or a
Variants of Shift-Or extend the approach to approximate matching, such as allowing a limited number of errors,
Applications include fast exact pattern search in text processing, DNA sequence analysis, and high-performance search tools.