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.

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.

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.

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).

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.

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.

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.

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.

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.