Shift-And Bit-Parallel Matching

Worked Example

Let the pattern be aba (m = 3) and the text be ababa. We map each character to a bitmask indicating its positions in the pattern (0-indexed, where bit i is set if the character occurs at position i).

Pattern: aba
Masks:
  a -> 101 (binary, meaning position 0 and 2)
  b -> 010 (binary, meaning position 1)

Let D be our state vector, initially 000.
Text processing (D <- ((D << 1) | 1) & mask(text[i])):

i=0, char='a', mask=101
D <- ((000 << 1) | 1) & 101 = 001 & 101 = 001.

i=1, char='b', mask=010
D <- ((001 << 1) | 1) & 010 = 011 & 010 = 010.

i=2, char='a', mask=101
D <- ((010 << 1) | 1) & 101 = 101 & 101 = 101.
Bit m-1 (bit 2) is 1! Match found ending at 2 (starts at 0).

i=3, char='b', mask=010
D <- ((101 << 1) | 1) & 010 = 1011 & 010 = 010.

i=4, char='a', mask=101
D <- ((010 << 1) | 1) & 101 = 101 & 101 = 101.
Bit 2 is 1! Match found ending at 4 (starts at 2).

Expected Match count: 2. Match positions: 0,2.

Experiment

Explore how overlapping matches are preserved in real-time. Follow these steps:

1. Open the Shift-And Bit-Parallel Matching module.
2. Set Text to Alternating (which represents ababa).
3. Set Pattern to aba.
4. Set Prefix to Full to process the entire text.
5. Observe that the Match count correctly shows 2 matches (at index 0 and 2), tracking multiple prefixes simultaneously.

Limitations

The standard Shift-And algorithm is extremely efficient for short patterns that fit within a single machine word (typically 32 or 64 bits). When the pattern length m exceeds the word size, multiple words are needed to represent the bitmask D, increasing the complexity from O(n) to O(n ⌈ m/w ⌉), where w is the word size. For JavaScript's exact bitwise operations, m is limited to 31/32 bits without using BigInt, though for this demonstration we bound m ≤ 4.

References

Detailed analysis and variants can be found in the foundational paper: A New Approach to String Matching by Baeza-Yates and Gonnet (1992), establishing bit-parallel simulation of NFAs.