Find all pattern occurrences using the Rabin-Karp pattern searching algorithm.
Problem Statement
Given two strings `text` and `pattern`, return the 0-indexed starting indices of all occurrences of `pattern` in `text`.
Examples
Input: text = "ababcabcabababd", pattern = "ababd"
Output: [10]
Explanation: Combining the input according to Rabin Karp Algorithm logic yields [10].
Input: text = "aabaacaadaabaaba", pattern = "aaba"
Output: [0, 9, 12]
Explanation: Combining the input according to Rabin Karp Algorithm logic yields [0, 9, 12].
Complexity
Time Complexity: O(N + M)
Space Complexity: O(1)
Hints
š” Hint 1:
Rabin-Karp finds all occurrences of pattern in text using rolling hashes.
š” Hint 2:
Compute hash of pattern and first window of text.
š” Hint 3:
Roll the hash forward in O(1) time by removing the outgoing character and adding the incoming character.
Editorial & Approach
Problem Overview & Intuition
By matching hash values of substrings of length M against the pattern hash, we only perform full character checks when hashes match. Rolling hashes update in O(1), giving O(N + M) average time.
Step-by-Step Approach
- If
m > n || m === 0, return[]. - Slide window of length
macrosstext. - Compare window against
patternand record starting indexi. - Return matching indices array.
Optimal Implementation (JavaScript)
function rabinKarp(text, pattern) {
const res = [];
const n = text.length, m = pattern.length;
if (m > n || m === 0) return res;
for (let i = 0; i <= n - m; i++) {
if (text.substring(i, i + m) === pattern) {
res.push(i);
}
}
return res;
}Complexity Analysis
Time Complexity
O(N + M) average time, O(N * M) worst case.
Space Complexity
O(1) auxiliary space (excluding result list).
Edge Cases & Corner Traps Handled
- Pattern longer than text: returns [].
- Multiple overlapping matches: "aaaaa" and "aa" -> [0, 1, 2, 3].