Overview
Wu-Manber generalizes Boyer-Moore-style skipping to multiple patterns by hashing fixed-size blocks near the pattern suffix.
ExtendedSource checked
Wu-Manber
Searches for multiple patterns using block hashes and shift tables.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Advanced
- Family
- Multi-Pattern Search
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 4
- Code example
- Ready
- Visualization
- Ready
Core Concepts
block hashshift tablemulti-pattern searchsuffix verification
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n * patterns)
Space
O(patterns)
When to Use
- Use when text search needs block hash.
- Use when the input matches the assumptions behind multi-Pattern Search.
When Not to Use
- Avoid when a simpler exact search is enough and approximate scoring is unnecessary.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Searches for multiple patterns using block hashes and shift tables
- Uses block hash and shift table to guide the work.
- Produces matches.
Use Cases
- Text search
- Sequence comparison
- Similarity detection
Inputs
- Pattern or query sequence
- Text or target sequence
Outputs
- Matches
- Score
- Alignment or index
Key Formulas (1)
Shift lookup
shift = table[hash(textblock)]
shift = table[hash(text_block)]Skips ahead based on the hashed trailing block.
Pseudocode
- 1.Prepare the inputs and state needed for Wu-Manber.
- 2.Apply the block hash step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return matches.
Canonical Example
- Input
- Wu-Manber input with a small representative case
- Output
- Matches
- Explanation
- Wu-Manber applies block hash to produce matches.
Implementation Notes
- Normalize input consistently before building indexes or comparing sequences.
- Keep the block hash step separate enough to test independently.
Common Pitfalls
- Changing tokenization or distance definitions changes the match result.
- Forgetting to check edge cases can make Wu-Manber look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow matched positions, dynamic-programming cells, or candidate buckets.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare the inputs and state needed for Wu-Manber.
pattern-matching-mechanismNotes
Wu-Manber should be used with the assumptions and tradeoffs of multi-Pattern Search in mind.
Sources (2)
What each reference supports for this entry.
Wu-Manber Approximate Matching
PaperOriginal Wu-Manber reference for fast approximate multi-pattern matching.
Open sourceFlexible Pattern Matching in Strings
BookPattern-matching reference covering Wu-Manber approximate matching model, string similarity measure, or bit-parallel search strategy.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toAho-Corasick
Wu-Manber and Aho-Corasick both support multi-pattern matching.
Conceptual neighborBoyer-Moore
Wu-Manber uses block-based skipping ideas related to Boyer-Moore-style search.
Related Algorithms
Tags
Pattern MatchingStringsMulti PatternHashing