Introduction

Rabin-Karp and KMP are both substring-search algorithms, but they are optimized for different situations. KMP is attractive when you want deterministic linear-time behavior for one pattern. Rabin-Karp is attractive when rolling hashes make it cheap to test many candidate windows or many equal-length patterns.

KMP is strong for one pattern

KMP preprocesses the pattern into a longest-prefix-suffix table and uses that table to avoid rescanning text characters after mismatches.

Example:

1def build_lps(pattern: str) -> list[int]:
2    lps = [0] * len(pattern)
3    j = 0
4    i = 1
5
6    while i < len(pattern):
7        if pattern[i] == pattern[j]:
8            j += 1
9            lps[i] = j
10            i += 1
11        elif j > 0:
12            j = lps[j - 1]
13        else:
14            lps[i] = 0
15            i += 1
16    return lps
17
18
19def kmp_search(text: str, pattern: str) -> list[int]:
20    lps = build_lps(pattern)
21    i = j = 0
22    out = []
23
24    while i < len(text):
25        if text[i] == pattern[j]:
26            i += 1
27            j += 1
28            if j == len(pattern):
29                out.append(i - j)
30                j = lps[j - 1]
31        elif j > 0:
32            j = lps[j - 1]
33        else:
34            i += 1
35
36    return out

Use KMP when:

• you are searching for one pattern
• worst-case guarantees matter
• you do not want collision-based behavior

Rabin-Karp is hash-first searching

Rabin-Karp uses a rolling hash to compare the pattern hash against each text window hash. Only when hashes match do you verify the actual substring.

Example:

1def rabin_karp(text: str, pattern: str, base: int = 256, mod: int = 1_000_000_007) -> list[int]:
2    n, m = len(text), len(pattern)
3    if m > n:
4        return []
5
6    high = pow(base, m - 1, mod)
7    p_hash = w_hash = 0
8
9    for i in range(m):
10        p_hash = (p_hash * base + ord(pattern[i])) % mod
11        w_hash = (w_hash * base + ord(text[i])) % mod
12
13    out = []
14    for i in range(n - m + 1):
15        if p_hash == w_hash and text[i:i + m] == pattern:
16            out.append(i)
17        if i < n - m:
18            w_hash = (w_hash - ord(text[i]) * high) % mod
19            w_hash = (w_hash * base + ord(text[i + m])) % mod
20
21    return out

Use Rabin-Karp when:

• you want rolling-hash filtering
• many equal-length patterns are being checked
• average-case performance is more important than deterministic worst-case guarantees

The big practical difference

KMP is about structure inside one pattern. Rabin-Karp is about hash reuse across moving windows.

That leads to this rule of thumb:

• one pattern, deterministic behavior: KMP
• many equal-length patterns or hash-based filtering: Rabin-Karp

If you are scanning large text for many same-length signatures, Rabin-Karp can be more natural because you can store pattern hashes in a set and compare rolling window hashes against them efficiently.

Collision handling matters in Rabin-Karp

Rabin-Karp is not just "hash and done." A hash match is only a candidate match. You still need to verify the actual substring because collisions are possible.

That is the major tradeoff:

• elegant rolling window logic
• but collision-aware verification is required

KMP does not have this issue because it is not based on probabilistic hashing.

Common Pitfalls

The biggest mistake is choosing only by big-O notation. Real workloads differ in pattern count, adversarial inputs, and implementation complexity.

Another mistake is forgetting substring verification in Rabin-Karp. A hash match alone is not proof of equality.

Developers also rebuild KMP preprocessing repeatedly for the same pattern even when the pattern is reused many times. The prefix table is meant to be reused.

Finally, do not force Rabin-Karp onto a workload that only needs simple deterministic single-pattern search. In that case KMP is often the clearer choice.

Summary

• KMP is usually the better choice for one-pattern deterministic searching.
• Rabin-Karp is often attractive for rolling-hash workflows and many equal-length patterns.
• KMP avoids collision issues, while Rabin-Karp requires verification on hash matches.
• Pattern count and workload shape matter more than memorized slogans.
• Choose based on actual search structure, not just algorithm names.