Rabin-Karp String Search
Visualize the rolling hash and matching process of the Rabin-Karp algorithm.
Free theory articleVisualize the rolling hash and matching process of the Rabin-Karp algorithm.
Concept & interpretation
The Rabin-Karp algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin. It uses a sliding window hash to find one or more occurrences of a pattern string within a larger text string. Unlike naive string matching algorithms that compare strings character by character, Rabin-Karp calculates a numerical hash value for the pattern and for each successive substring of the text. If the hash values match, it performs a full character-by-character comparison to confirm the match and avoid spurious hits.