KMP pattern matching: a practical tutorial
String searching asks a deceptively simple question: does a short pattern occur inside a larger block of text? The answer powers log filters, route matching, editor find functions, biological-sequence tools and many programming challenges. A naïve search can compare almost every character with every possible starting position, so a long file or busy server turns a harmless lookup into avoidable work. The Knuth–Morris–Pratt method removes that repeated work by preparing the pattern before scanning the text.
KMP is especially useful when many records must be checked against the same search term. Its key is a prefix-function array that records how much of a partially matched pattern can be retained after a mismatch. The scan then moves forward through the text without restarting at each candidate. The result is linear-time searching with reusable preprocessing, making the technique valuable for both interviews and real applications.
Why substring searching deserves attention
Most text APIs already provide a find operation, so learning a manual matching method may seem unnecessary. The value becomes clearer when the requirement controls the data: exact matching inside a stream, overlapping occurrences, a fixed pattern applied to many records, or an explanation of what a library hides. It also builds durable knowledge about invariants and amortised analysis, both central to algorithm design. Readers who want related foundations can revisit data structures before comparing search techniques.
Local systems make the need tangible. A transport feed for Sydney buses or Melbourne trams may contain hundreds of route and stop names, while catalogues across Australia’s supermarket sector contain repeated fragments. Search code must also respect ordinary Australian usage: people may look for a “brekkie” deal or say they will meet “at arvo”, so exact matching can sit beneath alias normalisation rather than replace it. Small grocers and specialist retailers also need dependable search without the overhead of a specialised platform.
The prefix-function idea
For each position in a pattern, the prefix function stores the length of the longest proper prefix that is also a suffix of the pattern prefix ending there. “Proper” matters because the whole prefix cannot count itself. For the pattern ABABAC, the values are 0, 0, 1, 2, 3, 0: the prefix ABA is both a prefix and a suffix of ABABA, but nothing non-empty matches around C.
A prefix function reveals reusable information. Suppose the text begins ABABA and the pattern is ABABAC. The next character fails against C, but the matched text ends in ABA, exactly the information recorded by the prefix-function value 3. Instead of discarding the work and retrying at the next character, KMP falls back to a three-character partial match and tests whether the current character extends it.
This is the central invariant: the number of matched pattern characters never depends on how many earlier positions were tried. Characters can be compared more than once during a fallback, but each fallback decreases the match length, while each successful extension increases it. The number of increases and decreases is bounded by the text length, which is why the scan is linear rather than quadratic.
Building the prefix-function array
The array can be built in one pass. At each index, try to extend the previous partial match. On a mismatch, consult the value already stored for the shorter candidate; that value identifies the next possible suffix without rescanning the pattern.
def build_lps(pattern):
lps = [0] * len(pattern)
j = 0
for i in range(1, len(pattern)):
while j > 0 and pattern[i] != pattern[j]:
j = lps[j - 1]
if pattern[i] == pattern[j]:
j += 1
lps[i] = j
return lps
For ABABAC, the running values are 0, 0, 1, 2, 3, and 0. At the third character, A raises j from zero to one; at the fourth character, B raises it to two; at the fifth character, A raises it to three. The final C cannot extend ABA, so the loop falls back and records zero. Since j grows at most once per pattern character and falls only along values already computed, preprocessing takes O(m) time for a pattern of length m and stores O(m) integers.
Walking through the search phase
Searching uses the same fallback idea, but j now tracks how many pattern characters match the current text position. A successful character advances j. A mismatch replaces j with lps[j - 1], preserving the longest suffix that could begin another valid match. The text index never moves backwards.
j = 0
for ch in text:
while j > 0 and ch != pattern[j]:
j = lps[j - 1]
if ch == pattern[j]:
j += 1
if j == len(pattern):
record_match()
j = lps[j - 1]
With pattern ABABAC and text ABABAB, KMP matches ABABA, then finds that B does not match the final C. It falls back from five matched characters to three and tests B successfully as part of ABAB. The scan then ends with no occurrence, having reused the overlap rather than retrying several starting positions.
After reporting a full match, the reset to lps[j - 1] also allows overlapping matches. Searching AAAA in AAAAA therefore reports starts at positions zero and one. This matters for repeated tokens, repeated timetable markers and compressed data where occurrences can overlap.
Implementing KMP and comparing methods
The complete function below returns every starting index and keeps the text scan separate from pattern preprocessing.
def kmp_search(text: str, pattern: str) -> list[int]:
if not pattern:
return list(range(len(text) + 1))
lps = build_lps(pattern)
matches = []
j = 0
for i, ch in enumerate(text):
while j > 0 and ch != pattern[j]:
j = lps[j - 1]
if ch == pattern[j]:
j += 1
if j == len(pattern):
matches.append(i - len(pattern) + 1)
j = lps[j - 1]
return matches
For example, kmp_search("banana bandana", "ana") returns [1, 11]. The empty-pattern branch defines an occurrence at every boundary, including the start and end. If that convention is unsuitable, reject the empty pattern explicitly instead of allowing it to reach comparisons.
The trade-offs become clearer when the alternatives are placed side by side. Here, n is the text length and m is the pattern length.
| Method | Setup | Classic worst-case scan | Extra space | Main idea |
|---|---|---|---|---|
| Naive search | O(1) |
O(nm) |
O(1) |
Retry from each starting position |
| KMP | O(m) |
O(n) |
O(m) |
Reuse prefix and suffix information |
| Boyer–Moore | O(m) |
O(nm) |
O(m) |
Skip characters using pattern order |
| Rabin–Karp | O(m) |
O(nm) |
O(1) |
Compare rolling hashes for candidate windows |
KMP is not always the fastest practical choice. Python’s built-in str.find is highly optimised, and Boyer–Moore can be extremely quick on ordinary English because it examines the pattern’s last character first. KMP is attractive when predictable linear scanning, overlapping matches or a transparent implementation matter more than library-level tuning.
Complexity, edge cases and testing
For text length n and pattern length m, KMP takes O(n + m) total time: O(m) to construct the prefix-function array and O(n) for the scan. Auxiliary space is O(m), excluding returned match positions. This is called amortised linear time because the scan may perform several comparisons for one text character, but the total number of comparisons remains linear.
Edge cases deserve explicit decisions. A pattern longer than the text cannot match; an empty pattern needs a defined meaning; and matching is case-sensitive unless both sides are normalised. Unicode can also matter. Australian place names and community names may contain accented characters, and visually identical strings can use different Unicode representations, so applications may need normalisation before comparison rather than assuming one byte-per-character model.
A reliable test routine should compare the implementation with a simple brute-force oracle over many short, randomly generated strings, including repeated characters and patterns that overlap. Property-based testing is especially useful here: generate a text and pattern, find every valid start with an independent method, then assert that both results agree. Include boundary cases such as an empty text, a one-character pattern, a pattern equal to the text and a match at the final character.
Practical uses and study recommendations
The technique suits Australian data products with modest infrastructure requirements: matching station names in Transport for NSW records, finding products in catalogues from Woolworths and Coles, whose retail footprint strongly shapes Australia’s supermarket market, or searching fuel-price feeds where locations are described in kilometres and prices in cents per litre. Date-oriented datasets add another local wrinkle, since Australian interfaces commonly display DD/MM/YYYY; patterns for day and month values must follow that representation rather than assume US ordering.
A deliberate practice routine can make the invariant stick.
- Implement the prefix-function builder without copying the search function, then explain what every stored value represents.
- Trace
ABABACby hand, including each fallback and the final reset after a complete match. - Compare results with a brute-force matcher on repeated characters, overlapping patterns and random short inputs.
- Test empty inputs, a pattern longer than the text, case differences and a match at the final character.
- Study when a built-in search, a trie or a suffix automaton is the better tool instead of applying KMP automatically.
Once the fallback logic is understood, the algorithm becomes a model for reusable progress: preprocess a small structure, preserve partial work after failure and avoid repeating effort. That principle extends well beyond substring matching into parsing, tokenising and many streaming algorithms.