Overview
Shift-And builds a bit mask for each alphabet symbol and updates a bit-vector of active pattern prefixes as each text character is read.
CoreSource checked
Shift-And Algorithm
Uses bit masks to update all exact-match prefix states in parallel.
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 into one or a few machine words.
- Use when exact matching over a manageable alphabet is needed.
When Not to Use
- Avoid when the pattern is much longer than the available bit-vector representation.
- Avoid when approximate matching or complex scoring is required.
What It Does
- Precomputes character masks for the pattern
- Maintains active prefix-match states in a word
- Detects a match when the final pattern bit becomes active
Use Cases
- Exact matching for short patterns
- Bit-parallel string search
- Searching many texts with the same pattern
Inputs
- Text or sequence
- Pattern, index, or comparison sequence
Outputs
- Matches, alignment, index, or similarity value
Pseudocode
- 1.Build a bit mask for every pattern character
- 2.Set active = 0
- 3.For each text character c
- 4.Set active = ((active << 1) | 1) & mask[c]
- 5.If the final pattern bit is set, report a match
Canonical Example
- Input
- pattern 'aba', text 'ababa'
- Output
- matches ending at positions 2 and 4
- Explanation
- The active bit mask advances prefix states and reaches the final bit at each full match.
Implementation Notes
- Precompute mask[c] with 1 bits where c appears in the pattern.
- After each text character, shift the active-state mask and AND with mask[c].
- Check the final pattern bit for a match ending at the current position.
Common Pitfalls
- Bit numbering must match the update formula.
- Patterns longer than the word size need multiword handling.
- Character encodings must map consistently to masks.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow tracking active prefix matches with bit masks on a small exact string matching example.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Build a bit mask for every pattern character
pattern-matching-mechanismNotes
Shift-And is exact string matching; approximate variants need additional bit-vector states.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Shift-And Algorithm's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Shift-And 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-And Algorithm solve related pattern preprocessing problems with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toBit-Parallel Levenshtein
Shift-And Algorithm and Bit-Parallel Levenshtein solve related exact string matching problems with different assumptions and tradeoffs.
Alternative toShift-Or Algorithm
Shift-And Algorithm and Shift-Or Algorithm solve related exact string matching problems with different assumptions and tradeoffs.
Alternative toBNDM
Shift-And Algorithm and BNDM solve related exact string matching problems with different assumptions and tradeoffs.
Tags
Pattern MatchingStringsMatching