String Algorithms: KMP & Rabin-Karp

This is the advanced end of the string toolkit. Most string problems are solved with the patterns you already have — two pointers, sliding window, hash maps, DP. But a specific family — exact pattern matching and substring fingerprinting — has two classic linear-time algorithms worth knowing by name: KMP and Rabin-Karp. They come up at the hard end of interviews, and even if you rarely implement them in full, understanding the ideas sharpens how you think about strings.

The idea

The naive approach to “does pattern P occur in text T?” tries every starting position in T and compares character by character. When it hits a mismatch deep into P, it slides P forward by one and starts over from scratch. In the worst case (think T = "aaaa…a", P = "aaa…ab") that is O(n·m) — every window re-compares almost the whole pattern.

Both fast algorithms remove the wasted re-work, in different ways:

• KMP never moves the text pointer backward. It precomputes, for each position in the pattern, how much of a prefix of the pattern is also a suffix of what we’ve matched so far — so on a mismatch it knows exactly where in the pattern to resume. O(n + m).
• Rabin-Karp turns each length-m window into a number (a hash) and slides the window in O(1) using a rolling hash. It compares the pattern’s hash against each window’s hash and only does a full character check when the hashes collide. O(n + m) on average.

Worked example: KMP

The heart of KMP is the prefix function (also called the failure table or lps — “longest proper prefix which is also a suffix”). For each index i of the pattern, lps[i] is the length of the longest string that is both a proper prefix and a suffix of P[0..i]. On a mismatch at pattern position k, instead of resetting k to 0 we jump to lps[k-1] — the next-best already-matched prefix — and keep the text pointer where it is.

def strStr(haystack, needle):
    if not needle:
        return 0
    # 1) build the prefix function (lps) for the pattern
    lps = [0] * len(needle)
    k = 0
    for i in range(1, len(needle)):
        while k and needle[i] != needle[k]:
            k = lps[k - 1]            # fall back to the next-best prefix
        if needle[i] == needle[k]:
            k += 1
        lps[i] = k
    # 2) scan the text, never moving i backward
    k = 0
    for i in range(len(haystack)):
        while k and haystack[i] != needle[k]:
            k = lps[k - 1]
        if haystack[i] == needle[k]:
            k += 1
        if k == len(needle):
            return i - k + 1          # full match ends at i
    return -1
# strStr("sadbutsad", "sad") -> 0
# strStr("leetcode", "leeto") -> -1

The same while k: k = lps[k-1] fallback shows up in many KMP-based solutions — building the table and scanning the text are the same loop, which is a nice thing to point out in an interview.

Worked example: Rabin-Karp

Rabin-Karp treats a string window as a base-b number modulo a large prime. The trick is the rolling hash: when the window slides by one character, you subtract the leaving character’s contribution, multiply by the base, and add the entering character — all O(1) — instead of re-hashing the whole window.

def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    if m > n:
        return -1
    base, mod = 256, (1 << 61) - 1
    high = pow(base, m - 1, mod)
    p_hash = t_hash = 0
    for i in range(m):                       # hash of pattern and first window
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if p_hash == t_hash and text[i:i + m] == pattern:   # verify on hash hit
            return i
        if i < n - m:                        # roll the window forward
            t_hash = ((t_hash - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return -1
# rabin_karp("abracadabra", "cada") -> 4

Because two different windows can share a hash, you must do a real character comparison on a hash match — the hash is a filter, not a proof. With a good base and prime, collisions are rare and the average stays linear.

Rabin-Karp shines when you need to compare many substrings, not just find one pattern — “are there two equal substrings of length L?” becomes “do any two windows share a hash?”, which is exactly how you binary-search the longest duplicate substring.

When to reach for it

Signals: “find a substring / first occurrence” (either algorithm — though Python’s in is already fast); “repeated substring pattern” and “longest happy prefix” (the prefix function falls straight out of KMP); “shortest palindrome” (run KMP’s prefix function on s + '#' + reverse(s) to find the longest palindromic prefix); and “longest duplicate substring” / “distinct substrings” (binary-search the length and fingerprint windows with Rabin-Karp). If a problem is really about string periodicity or borders, think KMP; if it’s about comparing many windows by content, think rolling hash.

Pitfalls

• Hash collisions. A Rabin-Karp hash match is not a guarantee — always verify with a real comparison, or use a large prime modulus (and ideally double hashing) to make false positives astronomically unlikely.
• Modular arithmetic bugs. Keep every intermediate value reduced mod a large prime; a subtraction can go negative, so in languages without Python’s well-behaved % you must add mod back before reducing.
• Off-by-one in the prefix function. The fallback is k = lps[k-1], not lps[k], and the table is built with the same matching loop you use to scan — getting these subtly wrong is the classic KMP bug. Trace it on a tiny pattern like "aab" by hand once.

Recap

Naive matching is O(n·m) because it re-scans on every mismatch. KMP precomputes a prefix function so the text pointer never moves backward → O(n + m); Rabin-Karp uses a rolling hash to slide windows in O(1) and compares hashes first → O(n + m) average, verified on a hit. Use KMP for periodicity/borders (repeated-substring, shortest-palindrome, happy-prefix) and Rabin-Karp for comparing many windows (longest duplicate substring). Signal: exact matching, repeated/duplicate substrings, string periodicity.

Practice: 10 solved problems on string algorithms → — cover each one, solve it yourself, then check the tested code.

Almost there

That’s the string-algorithms pattern — and nearly the whole toolkit. Two more topics round it out for a complete NeetCode-150-style coverage: Math & Geometry (matrix manipulation and number tricks) and designing a data structure (LRU/LFU and friends). Then a capstone pulls it all together into a concrete study plan.

Next: Lesson 26 — Math & Geometry.