the Rabin-Karp algorithm

Comparing the pattern against every window of the text, character by character, is slow because each comparison can take up to m steps. Rabin-Karp replaces most of those full comparisons with a single cheap number comparison: it computes a short fingerprint (a hash) of the pattern, then slides a same-length window across the text, keeping the window's fingerprint up to date, and only bothers to compare actual characters when the two fingerprints agree. Most windows are dismissed in one arithmetic step.

The engine is a rolling hash. First compute h = hash(P) in O(m). Then compute the hash of the first text window T[0..m-1], and roll it forward one position at a time, each update costing O(1). At every window whose hash equals h, do a direct character-by-character check to confirm a true match and rule out a hash collision (two different strings sharing a hash). If the hashes differ, the strings certainly differ, so you skip the check entirely. With a good random prime modulus, false hash matches are rare, so the expected running time is O(n+m). The worst case, however, is O(n*m): an adversarial input (or unlucky modulus) could make every window collide, forcing a full check each time — so Rabin-Karp is a Monte Carlo-flavored method whose speed is a probabilistic expectation, not a guarantee.

Rabin-Karp's real superpower is not single-pattern search, where KMP's clean worst case is preferable, but searching for many patterns of the same length at once: hash all the patterns into a set, then each text window is checked against the whole set in O(1) expected time. This makes it a natural fit for plagiarism detection and finding any of thousands of fixed-length signatures in a stream. It also generalizes beautifully to two-dimensional pattern matching (finding a small image inside a big one). Just remember the verification step — skipping it turns a reliable algorithm into one that occasionally lies.