Rabin-Karp

Michael Rabin & Richard Karp, 1987

Rabin-Karp uses a rolling hash function to efficiently compute hash values for successive windows of the text. When the window hash matches the pattern hash, it performs a character-by-character verification to confirm the match. The rolling hash allows each new window's hash to be computed in constant time from the previous window. The visualization shows the sliding window, hash values, and verification process.