Introduction

Knuth-Morris-Pratt and Boyer-Moore are both exact string-matching algorithms that improve on naive search, but they optimize in different ways. KMP guarantees linear worst-case time by reusing prefix information, while Boyer-Moore often achieves better average-case speed by skipping farther ahead after mismatches. Choosing between them depends on pattern length, alphabet size, and whether worst-case guarantees matter more than average throughput. Practical performance differences usually come from input distribution and implementation details, not asymptotic notation alone.

KMP Core Idea

KMP preprocesses the pattern into a longest-prefix-suffix table, usually called LPS. During mismatch, it uses LPS to shift the pattern without moving the text index backward.

1def build_lps(pattern: str):
2    lps = [0] * len(pattern)
3    j = 0
4    for i in range(1, len(pattern)):
5        while j > 0 and pattern[i] != pattern[j]:
6            j = lps[j - 1]
7        if pattern[i] == pattern[j]:
8            j += 1
9            lps[i] = j
10    return lps
11
12print(build_lps("ababaca"))

KMP search then uses this table to continue from the best known prefix boundary.

1def kmp_search(text: str, pattern: str):
2    if not pattern:
3        return []
4    lps = build_lps(pattern)
5    j = 0
6    matches = []
7    for i, ch in enumerate(text):
8        while j > 0 and ch != pattern[j]:
9            j = lps[j - 1]
10        if ch == pattern[j]:
11            j += 1
12            if j == len(pattern):
13                matches.append(i - j + 1)
14                j = lps[j - 1]
15    return matches
16
17print(kmp_search("ababcababcab", "ababc"))

Boyer-Moore Core Idea

Boyer-Moore compares from right to left inside each alignment and uses heuristics to skip more text:

• bad-character rule
• good-suffix rule

A simplified bad-character-only variant:

1def bm_bad_char_table(pattern: str):
2    table = {}
3    for i, ch in enumerate(pattern):
4        table[ch] = i
5    return table
6
7
8def bm_bad_char_search(text: str, pattern: str):
9    if not pattern:
10        return []
11    m, n = len(pattern), len(text)
12    table = bm_bad_char_table(pattern)
13    out = []
14    s = 0
15
16    while s <= n - m:
17        j = m - 1
18        while j >= 0 and pattern[j] == text[s + j]:
19            j -= 1
20        if j < 0:
21            out.append(s)
22            s += 1
23        else:
24            last = table.get(text[s + j], -1)
25            s += max(1, j - last)
26
27    return out
28
29print(bm_bad_char_search("HERE IS A SIMPLE EXAMPLE", "EXAMPLE"))

Full Boyer-Moore with both heuristics is more complex but can skip much more on real text.

Complexity and Practical Behavior

KMP guarantees O(n + m) worst-case time, where n is text length and m is pattern length.

Boyer-Moore often performs fewer comparisons in practice, especially when:

• pattern is long
• alphabet is large
• mismatches occur near pattern end

Worst-case behavior of Boyer-Moore variants depends on implementation details and input characteristics.

Preprocessing and Reuse Considerations

If one pattern is searched many times, preprocessing cost matters less than search speed. Both algorithms preprocess the pattern, but Boyer-Moore preprocessing can be heavier due to multiple heuristic tables.

If patterns change frequently and are short, KMP simplicity can be attractive.

Streaming and Memory Access Patterns

KMP works naturally for streaming because it scans text left to right with stable progression.

Boyer-Moore is often stronger for in-memory text search where random access and larger skips are cheap.

This distinction matters in systems such as:

• log stream scanning
• on-disk index scans
• in-memory full-text filters

When to Choose Which

Use KMP when:

• worst-case linear guarantee is required
• streaming sequential input is common
• implementation simplicity and predictability matter

Use Boyer-Moore when:

• pattern length is moderate to large
• alphabet diversity is high
• average throughput is the main objective

Benchmark against real data distribution before finalizing.

Common Pitfalls

A common mistake is assuming Boyer-Moore is always faster. On short patterns or small alphabets, gains may disappear.

Another mistake is ignoring preprocessing cost when patterns are frequently changing.

A third mistake is comparing theoretical complexity only and skipping realistic benchmarking.

Teams also deploy custom implementations without enough edge-case testing for empty patterns, overlaps, and encoding concerns.

Summary

• KMP and Boyer-Moore are both exact matching algorithms but optimize different search behaviors.
• KMP offers robust linear worst-case guarantees with prefix-suffix preprocessing.
• Boyer-Moore often wins in average-case performance through aggressive skips.
• Workload characteristics should drive algorithm choice, not generic claims.
• Measure on production-like text and pattern sets before committing.