Naive matching and KMP

What this chapter covers

Finding a pattern inside a text is one of the most-run operations in computing — every search box, every grep, every Ctrl-F does it. The obvious method is to try the pattern at every position and compare character by character, and it works, but it has a nasty failure mode: on the wrong input it re-examines the same text characters over and over, costing O(n·m). The Knuth-Morris-Pratt algorithm fixes this with one idea — when a mismatch happens after several characters matched, those matched characters are information, a known prefix of the pattern, and you can use them to slide the pattern forward by more than one without ever re-reading text you've already passed. The text pointer never moves backward. This chapter builds the naive matcher, then KMP and its precomputed failure function, watches the pattern slide over a text without rewinding, and measures the gap on adversarial input: 25 times fewer character comparisons.

A bit of history

The algorithm was published in 1977 by Donald Knuth, James Morris, and Vaughan Pratt, but its discovery was a three-way convergence worth the story. Morris had worked it out in 1970 while writing a text editor and being annoyed by the naive search's backup; Pratt developed related ideas; and Knuth, studying a theorem of Stephen Cook about which languages a certain kind of automaton could recognize in linear time, derived essentially the same algorithm from pure theory. When the three realized they had independently found the same thing, they published jointly. That origin — one route from the practical irritation of a slow editor, another from automata theory — is a nice illustration that KMP is really about a machine: the failure function turns the pattern into a finite automaton that reads the text once, left to right, never rewinding. It was the first substring-search algorithm proven linear in the worst case, and it opened the field of efficient string matching that the rest of this tier explores.

The intuition

Watch the naive matcher fail. Searching for ababc in abababca, it matches abab and then hits a mismatch at the fifth character. The naive response is to shrug, slide the pattern one position right, and start comparing from scratch — re-reading text characters it already looked at. But that's wasteful, because it knows the last four text characters were abab, and it can reason about what that implies without re-reading them. The prefix abab has a proper prefix (ab) that equals its suffix (ab), which means after the mismatch the pattern can be slid so those two characters line up and matching resumes from the third character of the pattern — no rewind, no re-comparison.

That reasoning is captured, once, in the failure function (or prefix function): for each position in the pattern, the length of the longest proper prefix of the pattern-so-far that is also a suffix of it. When a mismatch occurs after matching j characters, the table says "you can act as if lps[j-1] characters had matched instead" — the pattern slides forward by j - lps[j-1] and the text pointer stays put. The beautiful part is that the failure function is itself built by running this same logic on the pattern against itself, in O(m). Once you have it, the search is a single left-to-right sweep of the text where i only ever increases: each text character is looked at essentially once, giving O(n). The pattern becomes a little state machine, and the text streams through it.

Complexity: how it scales

KMP is $O(n + m)$: $O(m)$ to build the failure table and $O(n)$ to scan the text, because the text pointer i advances monotonically through all n characters and the pattern pointer j, though it can fall back, falls back a total bounded by how much it advanced — an amortized argument that keeps the whole scan linear. The naive matcher is $O(n \cdot m)$ in the worst case. That worst case isn't exotic; it's a highly repetitive text and pattern, exactly what shows up in DNA, in logs, in any low-alphabet data. The face-off runs the classic adversarial input — a text of all as and a pattern of as ending in one b, which makes the naive matcher re-scan almost the whole pattern at every position:

On an 8000-character text with a 50-character pattern, the naive matcher made about 398,000 character comparisons while KMP made about 16,000 — roughly 25 times fewer, and the gap widens with the pattern length, because naive's cost is $n \cdot m$ while KMP's is $n + m$. The naive line climbs steeply; the KMP line barely rises. That difference is the value of never rewinding: on adversarial input naive re-reads each text character up to m times, KMP reads it essentially once. For random text over a large alphabet the two are closer (mismatches come fast, so naive rarely gets deep into the pattern), but KMP's guarantee — linear no matter the input — is what makes it safe where naive is a latent quadratic bomb.

What it's good at, what it isn't

KMP is the right tool when you need a guaranteed linear single-pattern search and can't risk the naive quadratic blowup — streaming data where you see each character once and can't rewind, real-time systems where worst-case latency matters, or highly repetitive text (biological sequences, sensor logs, binary protocols) where naive genuinely degrades. Its failure function is also a reusable object of independent value: it reveals the periodic structure of a string (the shortest period of s is len(s) - lps[-1]), which solves a family of string-periodicity problems, and the automaton view underlies streaming and hardware pattern matchers.

Where KMP is not the fastest is ordinary text search over a large alphabet, where Boyer-Moore (next chapters) is typically quicker in practice because it skips forward by scanning the pattern right-to-left and can leap over many characters at once — KMP examines every text character, Boyer-Moore often examines a fraction of them. For multiple patterns at once, Aho-Corasick generalizes KMP's automaton and is the right choice. And in everyday code you'd simply call str.find, whose C implementation uses a hybrid algorithm that's usually faster than a hand-written KMP. KMP's role is the guaranteed-linear foundation and the conceptual gateway, not necessarily the speed champion.

The data, or the inputs

The face-off runs the canonical adversarial case — a text of n copies of a and a pattern of 49 as followed by a b — and counts character comparisons for KMP versus the naive matcher as n grows, isolating the quadratic-versus-linear gap. Correctness is checked hard: on two thousand random text/pattern pairs over several alphabets, KMP's match positions must equal both Python's built-in str.find and the naive matcher, and the failure function is separately verified against its brute-force definition (the actual longest prefix-suffix at every position). The animation runs KMP searching for ababc in abababca, drawing the text and the sliding pattern as two rows of characters.

Build it, one function at a time

The failure function — the whole cleverness, the pattern matched against itself:

def prefix_function(pattern):
    """The failure table. lps[i] = length of the longest proper prefix of pattern[:i+1] that
    is also a suffix of it. Built in O(m) by extending the previous longest prefix-suffix and
    falling back through the table on mismatch — the same trick the search itself uses, run on
    the pattern against itself. This is the whole cleverness of KMP; the search is easy once
    you have it."""
    m = len(pattern)
    lps = [0] * m
    k = 0                                        # length of the current longest prefix-suffix
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]                        # fall back to the next-best prefix-suffix
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps

And the search that uses it — a single sweep where the text pointer never rewinds:

def kmp_search(text, pattern):
    """Every start index where `pattern` occurs in `text`. Walk the text with pointer i (never
    decreasing) and the pattern with pointer j; on a mismatch, slide the pattern using the
    failure table (j = lps[j-1]) instead of resetting to 0 and rewinding i. O(n + m). Returns
    (match_positions, comparisons) — the comparison count exposes why it beats naive search."""
    if not pattern:
        return list(range(len(text) + 1)), 0
    lps = prefix_function(pattern)
    matches = []
    comparisons = 0
    j = 0                                        # how many pattern chars currently match
    for i in range(len(text)):                   # i, the text pointer, only ever increases
        while j > 0 and text[i] != pattern[j]:
            comparisons += 1
            j = lps[j - 1]                        # use the table to slide, don't rewind i
        comparisons += 1
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)             # full match ending at i
            j = lps[j - 1]                        # keep scanning for overlapping matches
    return matches, comparisons

Watch it work

Here's KMP searching for ababc (bottom row) in abababca (top row). Blue is the character being compared this step; green cells matched at the current alignment; red is a mismatch. Watch what happens at the first mismatch: after abab matches, the fifth comparison fails — but instead of sliding the pattern one step and re-reading, KMP consults the failure table and slides the pattern so its ab prefix lines up with the ab that already matched, resuming from the middle of the pattern with the text pointer never moving back. The pattern appears to jump forward by more than one. A few comparisons later it locks onto the full match at position 2. The text characters, up top, are each read essentially once — the pattern does all the sliding:

The complete code

The from-scratch tab is KMP with its failure function; the library tab is the naive matcher it's compared against (and the built-in str.find reference used to check correctness). Flip between them — the naive version is shorter, and that shortness is exactly the trap: it's simple because it re-reads, and re-reading is what makes it quadratic.

"""Knuth-Morris-Pratt (KMP) — find every occurrence of a pattern in a text without ever
backing up in the text. The naive way to search slides the pattern one position and, on a
mismatch, throws away everything it just learned and re-compares from scratch — which on
adversarial input costs O(n·m). KMP's insight is that a mismatch is not ignorance: the
characters that DID match are a known prefix of the pattern, and that prefix often overlaps
a suffix of itself, so the pattern can be slid forward by more than one without missing
anything, and the text pointer never moves backward.

The magic is a small precomputed table, the PREFIX FUNCTION (or "failure function"): for
each position in the pattern, the length of the longest proper prefix that is also a suffix
of the pattern up to that point. That table says, on a mismatch after matching j characters,
"you can resume as if j' < j characters had matched" — skipping the re-comparisons the naive
search would redo. Build the table in O(m), scan in O(n), and matching is O(n+m).
"""


# region: prefix_function
def prefix_function(pattern):
    """The failure table. lps[i] = length of the longest proper prefix of pattern[:i+1] that
    is also a suffix of it. Built in O(m) by extending the previous longest prefix-suffix and
    falling back through the table on mismatch — the same trick the search itself uses, run on
    the pattern against itself. This is the whole cleverness of KMP; the search is easy once
    you have it."""
    m = len(pattern)
    lps = [0] * m
    k = 0                                        # length of the current longest prefix-suffix
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]                        # fall back to the next-best prefix-suffix
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    return lps
# endregion


# region: kmp_search
def kmp_search(text, pattern):
    """Every start index where `pattern` occurs in `text`. Walk the text with pointer i (never
    decreasing) and the pattern with pointer j; on a mismatch, slide the pattern using the
    failure table (j = lps[j-1]) instead of resetting to 0 and rewinding i. O(n + m). Returns
    (match_positions, comparisons) — the comparison count exposes why it beats naive search."""
    if not pattern:
        return list(range(len(text) + 1)), 0
    lps = prefix_function(pattern)
    matches = []
    comparisons = 0
    j = 0                                        # how many pattern chars currently match
    for i in range(len(text)):                   # i, the text pointer, only ever increases
        while j > 0 and text[i] != pattern[j]:
            comparisons += 1
            j = lps[j - 1]                        # use the table to slide, don't rewind i
        comparisons += 1
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)             # full match ending at i
            j = lps[j - 1]                        # keep scanning for overlapping matches
    return matches, comparisons
# endregion

"""The library counterpart and the contrast. In real code you never hand-roll substring
search — you use Python's built-in, which is C-fast:

    text.find(pattern)          # first occurrence, or -1
    pattern in text             # membership
    [m.start() for m in re.finditer(re.escape(pattern), text)]   # all occurrences

CPython's `str.find` uses a hybrid of Crochemore-Perrin ("two-way") and Boyer-Moore-Horspool
ideas, not textbook KMP, but the guarantee is the same linear-time worst case. `find_all_builtin`
below wraps it as the correctness reference (all occurrences). `naive_search` is the contrast
that makes KMP's point — the straightforward O(n·m) method that rewinds and re-compares, whose
comparison count blows up on adversarial input.
"""


# region: naive
def naive_search(text, pattern):
    """The obvious algorithm: try the pattern at every start position, comparing left to right,
    and on any mismatch abandon this position and try the next — re-examining text characters it
    already looked at. O(n·m) worst case. Returns (match_positions, comparisons)."""
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)), 0
    matches, comparisons = [], 0
    for start in range(n - m + 1):
        k = 0
        while k < m:
            comparisons += 1
            if text[start + k] != pattern[k]:
                break                             # mismatch → give up, slide by one, redo from k=0
            k += 1
        if k == m:
            matches.append(start)
    return matches, comparisons
# endregion


# region: builtin
def find_all_builtin(text, pattern):
    """All occurrences via Python's built-in str.find — the trusted reference for correctness."""
    if not pattern:
        return list(range(len(text) + 1))
    out, i = [], text.find(pattern)
    while i != -1:
        out.append(i)
        i = text.find(pattern, i + 1)             # +1 allows overlapping matches
    return out
# endregion

Scratch vs library

The comparison here is KMP against the naive matcher, and it's a clean example of a recurring theme: the simpler algorithm isn't wrong, it's fragile. Naive search gives correct answers and is often perfectly fast — on random English text it rarely gets more than a character or two into the pattern before a mismatch, so its practical cost is near-linear. But it has no floor: hand it repetitive input and it degrades to quadratic silently, the same latent-quadratic hazard as using Dijkstra on negative edges or the wrong pivot in quicksort. KMP trades a little precomputation and a table for a guarantee — linear, always, whatever the input. That's the engineering trade the string-matching literature keeps making: pay an O(m) setup to buy a worst-case bound. In production you'd call str.find, whose compiled hybrid beats a Python-level KMP; building KMP yourself is what makes the failure function — reused, in richer forms, by Boyer-Moore and Aho-Corasick ahead — something you understand rather than invoke.

Where you'll actually meet it

KMP and its failure function run throughout text processing. grep, text editors, and search boxes use linear-time matching (often Boyer-Moore or hybrids, with KMP's guarantee as the fallback). Bioinformatics tools search DNA and protein sequences, exactly the repetitive low-alphabet data where naive search collapses. Intrusion-detection and antivirus systems scan network streams for signature patterns in a single pass, which KMP's no-rewind property makes possible on streaming data. The failure function itself appears wherever string periodicity matters — finding the smallest repeating unit of a string, detecting tandem repeats, string compression. And KMP is the conceptual parent of Aho-Corasick, the multi-pattern matcher behind many of these same tools. Anywhere a single pattern must be found in a stream with a worst-case guarantee, KMP is the foundation.

Takeaways

KMP finds every occurrence of a pattern in $O(n+m)$ by precomputing a failure function — the longest proper prefix that is also a suffix at each position — and using it, on a mismatch, to slide the pattern forward without ever rewinding the text pointer. The failure table is built by the same logic run on the pattern against itself, and the linear scan follows from an amortized argument: the pattern pointer can only fall back as much as it advanced. Against the naive $O(n·m)$ matcher it made 25 times fewer comparisons on adversarial input, trading a small precomputation for a worst-case guarantee the naive method can't offer.

The next chapter attacks the same problem from a completely different angle. Rabin-Karp turns each length-m window of the text into a number via a rolling hash and compares numbers instead of strings — usually O(n+m), occasionally fooled by hash collisions, and uniquely suited to searching for many patterns or two-dimensional patterns at once. Where KMP is a deterministic automaton, Rabin-Karp is a probabilistic fingerprint, and the contrast between the two is the contrast between the two great strategies of string search.