Rabin–Karp is a classic string-search algorithm used to locate a pattern inside a larger text.
Instead of comparing every character of the pattern at every possible position, Rabin–Karp computes a hash of the pattern and compares it with hashes of equally sized windows in the text.
Its core idea is:
Compare hashes first, and perform an exact character comparison only when the hashes match.
The technique becomes particularly useful because of Rolling Hash, which allows the hash of the next window to be calculated from the previous one without hashing the entire window again.
Basic string-matching problem
Suppose:
Text: ABCCDDAEFG
Pattern: CDD
A naive approach compares the pattern against each possible window:
ABC
BCC
CCD
CDD ← match
Rabin–Karp instead computes hashes for these windows and only performs a full comparison when a hash matches the pattern hash.
Why hashing helps
Imagine:
Hash("CDD") = 79152
If a text window has a different hash, it cannot be the pattern under the intended hash calculation.
If its hash is equal, however, we still need verification because two different strings can occasionally produce the same hash.
That situation is known as a hash collision.
Hash collisions
A hash function maps a huge input space into a finite set of numeric values.
Therefore, two different strings may theoretically produce the same result:
Hash("ABC") = 105
Hash("XYZ") = 105
So Rabin–Karp follows this process:
Hash match
↓
Exact character comparison
↓
Real match or collision
This verification step preserves correctness.
What is Rolling Hash?
Suppose the current window is:
ABC
and the next window is:
BCD
Instead of hashing BCD from scratch, a rolling hash can:
- Remove the contribution of
A. - Shift the remaining hash.
- Add
D.
Conceptually:
ABC
↓ shift
BCD
This allows each new window hash to be updated efficiently.
Polynomial Rolling Hash
A common hash representation treats a string like a polynomial.
For:
ABC
a conceptual form is:
A × base² + B × base¹ + C
To keep values manageable, modular arithmetic is used:
hash = value % prime
A general pattern is:
hash = (
c0 × base^(m-1) +
c1 × base^(m-2) +
... +
cm-1
) % prime
Base and prime
Implementations commonly use values such as:
base = 256
prime = 101
The base helps combine character values, while the prime modulus limits the numeric range and influences collision behavior.
Production hashing strategies may require more careful choices than educational implementations.
Rabin–Karp step by step
Given:
Text = "ABCCDDAEFG"
Pattern = "CDD"
first calculate:
patternHash = Hash("CDD")
windowHash = Hash("ABC")
If they differ, slide the window:
ABC
↓
BCC
↓
CCD
↓
CDD
Each new hash is produced using the rolling update.
When the hash equals the pattern hash, compare the actual characters to confirm the match.
TypeScript implementation
function rabinKarp(
text: string,
pattern: string
): number {
const n = text.length;
const m = pattern.length;
if (m === 0) return 0;
if (m > n) return -1;
const base = 256;
const prime = 101;
let patternHash = 0;
let windowHash = 0;
let highOrder = 1;
for (let i = 0; i < m - 1; i++) {
highOrder = (highOrder * base) % prime;
}
for (let i = 0; i < m; i++) {
patternHash = (
base * patternHash + pattern.charCodeAt(i)
) % prime;
windowHash = (
base * windowHash + text.charCodeAt(i)
) % prime;
}
for (let i = 0; i <= n - m; i++) {
if (patternHash === windowHash) {
let matches = true;
for (let j = 0; j < m; j++) {
if (text[i + j] !== pattern[j]) {
matches = false;
break;
}
}
if (matches) {
return i;
}
}
if (i < n - m) {
windowHash = (
base * (
windowHash -
text.charCodeAt(i) * highOrder
) +
text.charCodeAt(i + m)
) % prime;
if (windowHash < 0) {
windowHash += prime;
}
}
}
return -1;
}
Example:
rabinKarp("ABCCDDAEFG", "CDD");
returns:
3
Rolling update formula
When moving from one window to the next, the conceptual formula is:
newHash = (
base × (
oldHash - oldChar × highOrder
) + newChar
) % prime
The high-order multiplier represents the contribution of the character leaving the window.
Why can the hash become negative?
In JavaScript, % is a remainder operation and may return a negative result for negative inputs.
After removing the old character, the temporary value may become negative.
A common correction is:
if (windowHash < 0) {
windowHash += prime;
}
Complexity
With a good hash distribution, Rabin–Karp typically performs very well.
Average behavior is commonly expressed as:
O(n + m)
However, the worst case is:
O(n × m)
because many hash collisions could force exact pattern verification at many positions.
Extra space in the standard single-pattern implementation is:
O(1)
excluding the input strings.
Rabin–Karp vs. naive search
Naive string matching can require:
O(n × m)
comparisons in the worst case.
Rabin–Karp uses hash filtering to avoid many full comparisons in normal conditions.
Its tradeoff is the need to handle hash collisions correctly.
Rabin–Karp vs. KMP
The two algorithms solve a similar problem using different ideas.
KMP
Uses pattern structure:
Prefixes
Suffixes
LPS array
and guarantees:
O(n + m)
Rabin–Karp
Uses:
Hashing
Rolling Hash
Verification
It has strong average performance, but its theoretical worst case can degrade to O(n × m).
Multiple-pattern matching
One interesting advantage of hash-based matching appears when many patterns have the same length.
Their hashes can be stored in a hash set:
Known pattern hashes
├── 10521
├── 83442
├── 99301
└── ...
Then each rolling text window can be checked against the set efficiently.
If a hash is present, an exact verification can identify the actual matching pattern.
Plagiarism and document similarity
Rolling hashes can be used to create fingerprints of document windows.
For example:
Document
↓
Fixed-size token windows
↓
Rolling hashes
↓
Fingerprint comparison
Long or repeated matching fingerprints can provide evidence of shared content.
Real plagiarism systems usually combine hashing with additional techniques such as tokenization, N-grams, fingerprints, and semantic similarity.
Duplicate-content detection
Rolling hashes are useful when scanning many consecutive substrings for duplicates.
Two windows with the same hash become candidate duplicates and can then be verified exactly.
This idea appears in areas such as:
- Document comparison
- Duplicate detection
- File processing
- Sequence analysis
DNA sequence matching
DNA can be represented as strings such as:
ACGTACGTACGT
A pattern such as:
TACG
can be searched using the same string-matching principles.
Practical bioinformatics software often uses more specialized algorithms, but Rabin–Karp remains a useful model for hash-based sequence searching.
Signature detection
A stream can conceptually be processed as overlapping windows:
Data Stream
↓
Sliding Windows
↓
Rolling Hash
↓
Known Signature Hashes
↓
Verification
This illustrates why hash-based filtering can be useful when checking large data against many known patterns.
Double hashing
Collision probability can be reduced by maintaining two independent hashes:
hash1 using prime1
hash2 using prime2
A candidate match is considered only when both hash values agree.
This is commonly called Double Hashing in string-hashing contexts.
Rolling hashes beyond Rabin–Karp
Rolling and polynomial hashes appear in many other problems:
- Longest Duplicate Substring
- Repeated Substring Search
- Substring Equality Queries
- Document Fingerprinting
- String Similarity
- Competitive Programming
This is why learning Rabin–Karp is useful even when another algorithm is eventually used for simple substring search.
Prefix hashes
Another useful variation precomputes hashes for every prefix of a string.
Then a substring hash can be derived using the hashes of two prefixes and polynomial arithmetic.
This approach is especially valuable when many substring-comparison queries are performed on the same text.
Finding all matches
Rabin–Karp can return every occurrence, including overlapping matches.
For example:
Text: AAAAA
Pattern: AA
matches occur at:
[0, 1, 2, 3]
The rolling window naturally allows the search to continue after each match.
Common mistakes
Trusting the hash alone
Hash equality should normally be followed by exact verification because collisions are possible.
Rehashing every window from scratch
Doing so removes the main advantage of Rolling Hash.
Forgetting modular arithmetic
Without a modulus, hash values can become extremely large and JavaScript numeric precision can become problematic.
Weak hash parameters
Poor base and modulus choices may increase collisions.
Incorrectly removing the outgoing character
Its polynomial positional weight must be removed correctly before shifting the hash.
Edge cases
Important cases include:
- Empty pattern
- Pattern longer than text
- Pattern identical to text
- Overlapping matches
- Unicode and character-encoding assumptions
- Multiple equal hashes caused by collisions
When should you use Rabin–Karp?
It is especially useful when:
- You want to understand Rolling Hash.
- Consecutive windows must be hashed efficiently.
- Multiple patterns of equal length are being checked.
- The problem involves repeated or duplicate substrings.
- Hash-based candidate filtering is helpful.
For everyday application code, built-in string-search APIs are generally preferable unless algorithmic control is specifically required.
Technical interview perspective
Rabin–Karp tests several concepts at once:
- Hashing
- Sliding windows
- Modular arithmetic
- String matching
- Collision handling
- Complexity analysis
Understanding the rolling update and collision verification is more important than memorizing a specific implementation.
Conclusion
Rabin–Karp searches for a pattern by combining substring hashing with a sliding window.
Its conceptual pipeline is:
Pattern → Hash
Text
↓
Sliding Window
↓
Rolling Hash
↓
Hash Comparison
↓
Exact Verification
Typical complexity:
Average: O(n + m)
Worst: O(n × m)
Space: O(1)
The most reusable idea from Rabin–Karp is Rolling Hash: efficiently updating the hash of a moving substring without recomputing it from scratch.