String Matching: Rabin–Karp and KMP

Find where a pattern (needle, length m) first appears in a text (haystack, length n). Only start positions 0..n-m are possible. The whole game is avoiding re-reading characters you already saw.

Naive search

• Try every start; compare the pattern char by char until full match or mismatch.
• Time O(n·m) worst (bad on near-misses like "aaaaab" / "aab"), space O(1).
• On a mismatch it slides forward by one and throws away what it learned — that waste is what the other two fix.

Rabin–Karp (rolling hash)

• Compare hashes of each m-window instead of characters; a hash match is a candidate, verify it directly to rule out collisions.
• Rolling hash updates in O(1): drop the left char’s weight, shift up a digit, add the new right char. Use a base (256) and a large prime mod (1_000_000_007).
• high = pow(base, m-1, mod) is the leftmost digit’s weight; % mod after each step (Python % stays non-negative).
• Time O(n + m) average, O(n·m) worst (pathological collisions); space O(1). Best when matching many same-length patterns at once.

window abc (hash H) --drop a, add d--> bcd (hash H') --drop b, add e--> cde

KMP (prefix table)

• Never moves backward in the text. On a mismatch, slide the pattern by the longest matched prefix that is also a suffix.
• lps[i] = length of the longest proper prefix of pattern[:i+1] that is also a suffix. Depends only on the pattern; build once in O(m). Example: lps("ababd") = [0,0,1,2,0].
• Search: keep j = chars matched; on mismatch j = lps[j-1] (never re-read text); on j == m report i - j + 1.
• Time O(n + m) worst (guaranteed, no bad inputs), space O(m).

When to use which

• Naive / built-in str.find / in: short text, or the default in real code (optimized C).
• Rabin–Karp: many patterns of one length, or 2-D matching — hash set makes “is this window one of mine?” O(1).
• KMP: need a guaranteed linear worst case, or a stream you cannot rewind.
• Interview cue: a scan re-examining seen characters wants a summary (hash, prefix table, counter) so it can move strictly forward.

Summary table