What is the KMP algorithm?

The Knuth-Morris-Pratt algorithm finds all occurrences of a pattern within a text in linear O(n+m) time by precomputing a failure function so the text cursor never moves backwards.

Why does the text cursor never move back?

On a mismatch the failure function tells KMP how much of the pattern already matched as a prefix, so it shifts the pattern rather than rewinding the text. Each text character is examined at most a constant number of times.

How is KMP faster than naive search?

Naive search can re-compare characters after every shift, giving O(n*m) in the worst case. KMP reuses information from previous comparisons, achieving O(n+m).

How is the failure function computed?

It is built by matching the pattern against itself: a pointer tracks the current prefix length, extending on a match and falling back through earlier failure values on a mismatch, all in O(m) time.

What is the time and space complexity?

KMP runs in O(n+m) time, where n is the text length and m the pattern length, and uses O(m) extra space for the failure table.

Can KMP find overlapping matches?

Yes. After a full match it uses the failure value of the last pattern position to continue, so overlapping occurrences such as AA in AAAA are all reported.

Text editors, grep-style search, intrusion detection, bioinformatics and network packet inspection use KMP or related linear-time matching algorithms.

How does KMP compare with Boyer-Moore?

Boyer-Moore scans the pattern from right to left and can skip large chunks, often faster in practice, while KMP guarantees a strict linear bound and never moves the text cursor backwards.

What happens if the pattern is empty?

An empty pattern matches at every position by convention. This simulation expects a non-empty pattern shorter than or equal to the text for a meaningful search.

Home▸Algorithms & AI▸KMP String Matching — Failure Function

🔎 KMP String Matching — Failure Function

Knuth-Morris-Pratt searches text in O(n+m): a prefix failure function lets the pattern slide forward without re-checking matched characters. Watch the cursor never backtrack.

Algorithms & AI3DModerate60 FPS

About KMP String Search

The Knuth-Morris-Pratt (KMP) algorithm solves the string-matching problem — finding all occurrences of a pattern P of length m inside a text T of length n — in O(n + m) time, compared to the naïve O(mn) worst case. The key insight, published by Donald Knuth, Vaughan Pratt, and James Morris in 1977, is the failure function (also called the prefix function): a precomputed table that encodes, for each position in the pattern, the length of the longest proper prefix that is also a suffix. When a mismatch occurs, the algorithm uses this table to skip the pattern forward without re-examining any text character already processed.

The simulation animates two pointers — one over the text and one over the pattern — highlighting matched characters in green and mismatches in red. You can see the failure-function table being built, watch the pattern slide forward on a mismatch, and compare the total character comparisons against a naive brute-force counter shown alongside.

Frequently Asked Questions

Why is KMP faster than naive string matching?

Naive search can re-examine the same text characters many times: on a text like "AAAAAAB" with pattern "AAAB", it performs O(nm) comparisons in the worst case. KMP avoids this by never moving the text pointer backwards; each character is examined at most twice (once in the failure-function build, once in the search), giving a firm O(n + m) guarantee regardless of the input.

What is the failure function (prefix function)?

For a pattern P, the failure function π[i] gives the length of the longest proper prefix of P[0..i] that is also a suffix of P[0..i]. For example, for pattern "ABAB", π = [0, 0, 1, 2]. When a mismatch occurs at position i in the pattern, the algorithm sets i = π[i−1] instead of resetting to 0, so previously matched characters are not re-compared.

What is the time complexity of building the failure function?

Constructing the failure table takes O(m) time and O(m) space using a two-pointer scan of the pattern itself. Combined with the O(n) search phase, the total complexity is O(n + m). The proof uses an amortised argument: although the inner loop can iterate, the variable tracking match length can only increase n times across the entire search.

How does KMP handle overlapping matches?

When a full match is found at position i in the text, the algorithm sets the pattern pointer to π[m−1] rather than 0, allowing it to immediately search for the next overlapping match. For example, searching for "ABA" in "ABABA" correctly finds matches at both positions 0 and 2.

Is KMP the fastest string-matching algorithm in practice?

Not always. While KMP achieves the theoretical O(n + m) bound, algorithms like Boyer-Moore-Horspool often outperform it in practice because they can skip many characters at once using bad-character and good-suffix heuristics, resulting in sub-linear average-case behaviour on typical English text. KMP is preferred when the alphabet is small (e.g., DNA bases A/C/G/T) or when streaming input precludes look-ahead.

Where is KMP used in real software?

KMP and its relatives are used in grep, text editors, bioinformatics tools (DNA sequence alignment), network intrusion detection systems (pattern matching in packet payloads), and antivirus signature scanning. The Linux kernel uses a variation for string searching in kernel modules.

What is the difference between KMP and the Aho-Corasick algorithm?

KMP searches for a single pattern in linear time. Aho-Corasick generalises this to simultaneously search for k patterns in O(n + m₁ + … + mₖ + z) time (z = total matches), using a finite automaton built from all patterns. It is the algorithm behind tools like fgrep and network content inspection systems.

Can KMP handle Unicode text?

Yes, provided characters are compared correctly. KMP operates on sequences of tokens (code points or bytes), so it works on any alphabet. When using UTF-8 encoded text it is common to operate on bytes, but care is needed near multibyte character boundaries to avoid splitting a codepoint mid-match.

What is the Z-algorithm and how does it relate to KMP?

The Z-algorithm computes for each position i in a string the length of the longest substring starting at i that is also a prefix of the string. It solves the same pattern-matching problem in O(n + m) time but uses a different approach: it concatenates P + $ + T and computes the Z-array, then finds matches where Z[i] ≥ m. Many competitive programmers prefer Z-arrays for their conceptual simplicity.

Why does the text pointer never move backwards in KMP?

This is the algorithm's central invariant. The failure function guarantees that when a mismatch occurs at pattern position i, all information about the text characters already scanned is encoded in π[i−1]. There is therefore never any need to re-examine a text character that has already been matched, which is what yields the linear time bound.

⚙ Under the hood

Knuth-Morris-Pratt searches text in O(n+m): a prefix failure function lets the pattern slide forward without re-checking matched characters. Watch the cursor never backtrack.

KMPstring matchingfailure functionprefix tableCanvas 2D

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install