Implementing Knuth-Morris-Pratt Pattern Matching

String pattern matching asks a deceptively simple question: where does a shorter sequence first appear inside a longer one? A text editor using find, a validator checking an incoming record, and a log analyser looking for an incident phrase all rely on this operation. The challenge grows from correctness for a single short string to predictable speed as the input expands. A direct scan can compare the same characters repeatedly, giving O(nm) worst-case time for text length n and pattern length m. Learn more about Understanding The Dbscan Clustering Algorithm For Density Based Clustering.

The Knuth–Morris–Pratt algorithm removes that repeated work by preprocessing the pattern into failure information. Instead of restarting after a mismatch, it reuses the longest prefix already matched. The result is O(n+m) worst-case time and O(m) auxiliary space, with total fallback work bounded by the text length. This makes the method useful for exact substring searches in datasets, streamed input, and interactive tools, while remaining small enough to understand line by line.

For Australian developers, subtle local differences are worth considering: spellings such as analyse and optimise may differ from US logs, and dates may follow the day-first 08/03/2026 convention. A Sydney fintech team might search ledger descriptions, a Melbourne operations group might scan incident reports for a Victoria route code, and a Brisbane service might match update templates carrying a Queensland code. These examples show why matching rules should be explicit rather than hidden in regular expressions.

Why Linear-Time Pattern Matching Matters

Exact matching means contiguous characters, not merely the same words in any order. A validator may accept Brisbane Office anywhere in an address but need Office Brisbane as one continuous substring. KMP handles the stricter case. It does not tokenise, ignore punctuation, or interpret wildcards; preprocessing the pattern alone allows it to locate exact occurrences efficiently and report every overlapping match.

In Australian back-office and logistics workflows, exact matching often sits below a friendlier interface. Sydney-based finance teams may need to locate PAYMENT-CLEARED in imported statement files, while Canberra agencies may search public datasets for a fixed CC-BY-4.0 licence marker. The hidden matcher should therefore return positions, not just a yes-or-no answer, so callers can extract surrounding fields and preserve traceability.

This differs from tasks that learn relationships among examples. For instance, density-based clustering with DBSCAN groups records according to neighbourhood density rather than locating a predetermined character sequence. Both techniques can appear in the same data pipeline, but their guarantees and data models are separate: clustering assigns structure, while KMP reports literal offsets.

Building the Failure Function

The failure function, often called the LPS array, stores a number for each pattern position. At index i, lps[i] is the length of the longest proper prefix of pattern[:i+1] that is also a suffix. “Proper” matters because the whole string is not allowed to match itself in this definition. When a comparison fails, the matcher consults this array to identify how much of the current match can be retained.

For the pattern ABABACABA, the LPS values are 0, 0, 1, 2, 3, 0, 1, 2, 3. After matching ABAB, a failing character can fall back to the prefix AB, which is already known to match, rather than beginning again at the first character. This shift is the central optimisation: previously earned comparisons are reused, not discarded.

The LPS array can be built with the same fallback idea. A candidate length tracks the current matching prefix; a mismatch reduces it to lps[length-1], and a successful character increases it by one. Each increase is bounded by the pattern length, while every fallback strictly decreases the candidate length, so construction takes O(m) time rather than repeatedly comparing prefixes from scratch.

Implementing KMP in Python

Below is a Python 3.9+ implementation that returns every starting index, including overlapping occurrences. It deliberately rejects an empty pattern because most callers need a meaningful non-empty target, and the built-in str.find treats an empty needle as an immediate match. The LPS array is computed once, then reused during the scan.

def build_lps(pattern: str) -> list[int]:
    lps = [0] * len(pattern)
    length = 0

    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = lps[length - 1]

        if pattern[i] == pattern[length]:
            length += 1

        lps[i] = length

    return lps


def find_occurrences(text: str, pattern: str) -> list[int]:
    if not pattern:
        raise ValueError("pattern must not be empty")

    lps = build_lps(pattern)
    matches: list[int] = []
    length = 0

    for i, char in enumerate(text):
        while length > 0 and char != pattern[length]:
            length = lps[length - 1]

        if char == pattern[length]:
            length += 1

        if length == len(pattern):
            matches.append(i - len(pattern) + 1)
            length = lps[length - 1]

    return matches

The important post-match line sets length to lps[length-1] instead of zero. That preserves a valid partial match, which is what lets the function find overlapping results such as ABAB at offsets 0, 2, and 4 in ABABABAB. The search remains linear: each text position advances the scan, and failed comparisons use LPS information instead of reopening earlier text.

This implementation performs lexical matching, not probabilistic classification. When a system must assign categories from word counts rather than locate exact text, Naive Bayes text classification follows a different model. Keeping that distinction clear helps prevent a linear string algorithm from being used where token frequencies, priors, and probabilities are required.

Tracing Matches and Comparing Alternatives

Several search strategies can find substrings, but they differ in preprocessing, guarantees, memory use, and output handling. Here, n is text length, m is pattern length, L is the total dictionary length, and z is the number of reported matches.

Method	Preprocessing	Search time	Auxiliary space	Best fit
Naive scan	None	O(nm)	O(1)	Very short text and pattern
KMP	O(m)	O(n+m)	O(m)	One exact pattern with overlaps
Rabin–Karp	O(m)	Expected O(n+m); worst O(nm)	O(1)	Hash-based probabilistic comparison
Aho–Corasick	O(L)	O(n+L+z)	O(L)	Many fixed patterns in one pass

Consider the text ABABABAB and the pattern ABAB. The matcher reaches a complete match at index 3, reports start index 0, and falls back to a matched length of 2 because the prefix AB is also a suffix of the completed pattern. It continues through the next two characters and reaches a second match ending at index 6, reporting start index 2. The same fallback permits a third match starting at index 4.

A trace can become noisy if it prints every internal fallback. For tests, assert the returned offsets, the count of matches, and one boundary case at a time. For large data, record elapsed time only after correctness is established; a fast wrong search is not evidence that the LPS array is sound.

Naive scanning remains reasonable for a short pattern or tiny text because its constant factor is small. Aho–Corasick becomes preferable when many fixed patterns must be found in one pass, while Rabin–Karp can be useful when hash-based comparison matches a broader design. KMP is the balanced choice for one exact pattern with deterministic linear behaviour.

Common Pitfalls and Edge Cases

Most implementation bugs come from ambiguous boundary rules rather than the core idea. During LPS construction, pattern[length] must remain within the pattern; during scanning, pattern[length] must be valid before a comparison. After a full match, resetting to zero loses overlaps, while resetting to the wrong LPS entry can cause an out-of-range access or an infinite loop.

The Python version scans Unicode code points. A byte-oriented variant must encode both inputs consistently and understand UTF-8 boundaries; otherwise, a match could begin inside a multibyte character. Unicode normalisation can also matter for names and accented text, while case folding depends on the product’s rules. Australian English content may contain optimise beside optimize in imported records, and KMP will not treat those spellings as equivalent unless the caller normalises them first.

KMP assumes a linear sequence and a fixed alphabet, so it does not solve graph connectivity. For connected weighted graphs, a minimum spanning tree guide describes a different problem with different guarantees. Within KMP, property-based tests can generate random texts and patterns and compare every returned offset with a trusted but simple reference implementation.

Performance, Testing, and Usage Recommendations

Linear complexity does not guarantee that a Python KMP loop will outperform every library routine. Built-in search functions use optimised native code, so benchmark KMP against str.find or regular expressions when both are credible choices. Measure realistic Australian workloads such as statement imports, support-ticket exports, and application logs, including memory use and the cost of constructing the LPS array for repeated searches of the same pattern.

The following practices keep the implementation dependable in tutorials and production services:

• State the contract. Decide whether matching is case-sensitive, whether Unicode is normalised, and whether an empty pattern is valid. Encoding these decisions prevents callers from receiving offsets under different assumptions.
• Separate preprocessing from searching. Build the LPS array once per pattern, then reuse it across many texts. This reflects how repeated searches for a fixed product code or incident phrase occur in batch jobs.
• Preserve overlap deliberately. After a complete match, reset the matched length with lps[length-1]. A reset to zero is simpler but silently changes the result for patterns that overlap.
• Test the boundaries. Include empty text, a one-character pattern, a pattern longer than the text, matches at both ends, repeated characters, and a mismatch at the final position. Compare results with a small reference search.
• Normalise deliberately. Apply the same lowercasing, Unicode normalisation, and whitespace policy to the text and pattern before preprocessing. Changing only one side can prevent an otherwise valid match.

Together, the LPS construction and scan express a useful principle: preprocess once, preserve valid partial matches, and avoid repeated work. This gives KMP deterministic linear-time behaviour, exact offsets, and predictable resource use, making it a strong fit for educational implementations and services that repeatedly search streamed or indexed text.