🔎 KMP String Matching
Failure function search
Step 0
Matches: 0
Inputs
Controls
Stats
Comparisons
0
Matches
0
Phase
Failure
Status
Ready
Trace
Info & Theory

Knuth-Morris-Pratt (KMP) searches for a pattern inside a text in O(n+m) time, where n is the text length and m the pattern length.

The failure function

For each position q of the pattern, fail[q] is the length of the longest proper prefix of P[0..q] that is also a suffix. It is computed by matching the pattern against itself in O(m) time.

The scan

Walk one cursor i through the text and a cursor q through the pattern. On a match both advance. On a mismatch with q > 0, set q = fail[q−1] — the pattern slides forward while i stays put. The text cursor never moves back.

Why it is linear

Each step either advances i or decreases q. Since q can only rise as many times as i advances, the total work is O(n+m).

Where it is used

Editor search, grep, intrusion-detection signature scanning and bioinformatics all use KMP or related linear-time matchers.

Frequently asked questions

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.

What is the failure function?

The failure (prefix) function records, for each position in the pattern, the length of the longest proper prefix that is also a suffix. It tells the algorithm how far to slide the pattern after a mismatch.

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.

Where is KMP used?

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.

About KMP String Search

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

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.