A string-matching algorithm that uses a rolling hash to compare a pattern against every window of a text in roughly constant time per position, checking a full character comparison only when the hashes agree; well suited to searching for several patterns at once.
Facts
Core PrincipleA string-searching algorithm that computes a rolling hash of the search pattern and of each equal-length window of the text, comparing hashes first so that only windows with a matching hash are checked character by character against the pattern. 1 Connections
In Field
Invented
Michael O. Rabin co-developed the string search algorithm with Richard M. Karp, published in 1987.
Richard M. Karp co-developed the string search algorithm with Michael O. Rabin, published in 1987.
Sources
1. Wikipedia: Rabin-Karp algorithm
Wikimedia FoundationLead section, first paragraphQuote, Lead section, first paragraph
It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.