Rabin-Karp Algorithm

KMP is fast for one pattern but searching for 1,000 patterns in the same text means 1,000 passes through it. Rabin-Karp takes a different approach: hash each window of the text and compare the hash to the pattern's hash. Equal hashes trigger a character-by-character verification; unequal hashes are skipped in O(1). With a rolling hash, the hash of each new window is computed from the previous one in O(1).

This chapter covers the rolling hash, modular arithmetic, the full algorithm, collision handling, and multi-pattern search.