Overview
Rabin-Karp hashes the pattern and each same-length text window, then verifies characters when hashes match.
CoreSource checked
Rabin-Karp
Searches for a pattern by comparing rolling hash values.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pattern Matching
- Difficulty
- Intermediate
- Family
- Hash-Based Matching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Rabin-Karp String Search
Core Concepts
rolling hashwindow comparisoncollision checkpattern hashpattern comparisonstring sequencehash functionhash-based matching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + m)
Average
O(n + m)
Worst
O(nm)
Space
O(1)
When to Use
- Use Rabin-Karp when you need to compute rolling window hashes.
- Use it for multiple pattern search with inputs like text.
- Use it when exact, fuzzy, or structured patterns must be found in sequences.
- Use it when the Hash-Based Matching tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when preprocessing cost is larger than a one-off simple scan.
- Do not treat the O(n + m) average case as a guarantee; check the O(nm) worst case.
- Avoid it when the required output is not match positions.
What It Does
- Computes rolling window hashes
- Verifies possible matches
Use Cases
- Multiple pattern search
- Plagiarism checks
- Finding repeated substrings
Inputs
- Text
- Pattern
- Hash function
Outputs
- Match positions
Key Formulas (1)
Rolling hash
hashnext = (base · (hash − old · base(m − 1)) + new) mod prime
hash_next = (base * (hash - old * base^(m - 1)) + new) mod primeUpdates the window hash after dropping one character and adding another.
Pseudocode
- 1.Hash the pattern
- 2.Hash the first text window
- 3.Compare hashes for the current window
- 4.Verify characters when hashes match
- 5.Roll the hash to the next window
Canonical Example
- Input
- text = "abracadabra", pattern = "cad"
- Output
- match at index 4
- Explanation
- The rolling hash scans windows and verifies the window whose hash matches the pattern.
Implementation Notes
- Use a rolling hash to update each window in constant time.
- Verify candidate matches with direct comparison after hash equality.
- Keep arithmetic normalized after subtraction.
Common Pitfalls
- Treating equal hash values as guaranteed matches.
- Choosing a modulus or base that causes too many collisions.
- Forgetting to remove the outgoing character from the rolling hash.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow a fixed-size text window moving while its hash updates.
Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Hash the pattern
rolling-hash-windowNotes
Hash collisions require a character check before reporting a match.
Sources (2)
What each reference supports for this entry.
Algorithms on Strings, Trees, and Sequences
BookString algorithms reference for Rabin-Karp's pattern matching, suffix indexing, alignment, or sequence-processing mechanism.
Open sourceIntroduction to Algorithms (CLRS)
BookTextbook support for Rabin-Karp's algorithm family, complexity framing, and standard implementation concepts.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toKnuth-Morris-Pratt
Rabin-Karp uses rolling hashes rather than prefix automata.
Conceptual neighborMinHash
Rabin-Karp uses rolling hashes for exact pattern search, while MinHash uses hashes for approximate set similarity.
Related Algorithms
Tags
Pattern MatchingStringsRolling HashHashing