Overview
Shift-Or is the complement-style sibling of Shift-And: it precomputes character masks and updates a bit-vector as the text is scanned, reporting a match when the final state bit clears.
CoreSource checked
Shift-Or Algorithm
Performs exact string matching with bit masks that track unmatched pattern positions.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Bit-Parallel String Matching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 13
- Code example
- Ready
- Visualization
- Ready
Core Concepts
exact string matchingbit-parallel string matchingmatchingbit maskspattern matching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n + m)
Worst
O(n + m)
Space
O(n + m)
When to Use
- Use when the pattern fits in machine-word bit masks.
- Use when exact matching is needed and bit-parallel updates are attractive.
When Not to Use
- Avoid when the pattern is longer than the supported bit-vector representation unless using a multiword version.
- Avoid when approximate matching or scoring is required.
What It Does
- Computes bit-parallel string matching within Bit-Parallel String Matching workloads (O(n + m) time, O(n + m) space).
- Works by Performs exact string matching with bit masks that track unmatched pattern positions.
- Maintains key invariants across exact string matching, bit-parallel string matching, matching.
Use Cases
- Production and research workloads requiring bit-parallel string matching via Performs exact string matching with bit masks that track unmatched pattern positions.
- Bit-Parallel String Matching pipelines where O(n + m) time and O(n + m) space fit system constraints.
- Engineering comparisons against Bit-Parallel Levenshtein and Shift-And Algorithm when tuning bit-parallel string matching.
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Pseudocode
- 1.Build inverted masks for pattern characters
- 2.Initialize state to all 1 bits
- 3.For each text character c
- 4.Update state = (state << 1) OR mask[c]
- 5.If the accepting bit is 0, report a match
Canonical Example
- Input
- pattern 'aba', text 'ababa'
- Output
- matches ending at positions 2 and 4
- Explanation
- The bit-vector reaches the accepting bit for each exact occurrence of the pattern.
Implementation Notes
- Initialize all state bits to 1 under the Shift-Or convention.
- Clear bits in character masks where the character appears in the pattern.
- Report a match when the chosen final-state bit becomes 0.
Common Pitfalls
- Shift-Or uses inverted bit conventions compared with Shift-And.
- The match bit and mask initialization must agree.
- Long patterns need careful carry handling across words.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow using inverted bit masks to update matching states per character on a small exact string matching example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Build inverted masks for pattern characters
pattern-matching-mechanismNotes
The algorithm is compact but easy to get backwards because the active states are represented with cleared bits.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Shift-Or Algorithm's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Shift-Or Algorithm's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesHorspool Algorithm
Pattern Matching · Core
Both address exact string matching, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesKasai LCP Algorithm
Pattern Matching · Core
Both address longest common prefix array, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesMorris-Pratt
Pattern Matching · Core
Both address exact string matching, but they make different modeling or performance tradeoffs.
Compare with thisAlternativesPrefix Function
Pattern Matching · Core
Prefix Function and Shift-Or Algorithm solve related pattern preprocessing problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toBit-Parallel Levenshtein
Shift-Or Algorithm and Bit-Parallel Levenshtein solve related exact string matching problems with different assumptions and tradeoffs.
Alternative toShift-And Algorithm
Shift-Or Algorithm and Shift-And Algorithm solve related exact string matching problems with different assumptions and tradeoffs.
Alternative toBNDM
Shift-Or Algorithm and BNDM solve related exact string matching problems with different assumptions and tradeoffs.
Tags
Pattern MatchingStringsMatching