Algorithms and Data Structures · Senior · Question 21 of 75
What is the key idea of the Rabin-Karp string search?
- ✓Correct answer: A rolling hash compares the pattern with each window in O(1)
- 2It skips ahead based on the last character of the pattern
- 3It builds a trie of all suffixes of the text
Explanation
When the window slides by one character, the hash is updated by removing the old character and adding the new one. Only windows with a matching hash are compared character by character. It shines when searching for many patterns at once.