KMP String Matching

Build a prefix-suffix table and replay exact string search with fallback, overlapping matches and a text cursor that never rewinds.

Concept Overview

The Knuth-Morris-Pratt algorithm finds every exact occurrence of a pattern in a text. It preprocesses the pattern into a table of reusable prefix lengths. After a mismatch, the table identifies the part of the previous match that is still useful, so the text cursor never needs to move backward. A retained border after a full match also preserves overlapping occurrences.

Mathematical Definition

Let T have length n and a nonempty pattern P have length m. Indices are zero based, and P[a..b) includes a but excludes b. For each pattern index k, the prefix function stores the length of the longest proper prefix that is also a suffix of P[0..k + 1).

prefix[k] = max ℓ such that 0 ≤ ℓ ≤ k and P[0..ℓ) = P[k + 1 − ℓ..k + 1).

Before a comparison: T[i − j..i) = P[0..j).

Mismatch with j > 0: j ← prefix[j − 1], while i is unchanged.

Full match: report i − m, then j ← prefix[m − 1].

The maximum is over integer lengths and always includes zero. A proper prefix is shorter than the string being inspected. The match-reporting formula uses the text cursor after the final matched letter has advanced it. Falling back follows shorter borders until a comparison can continue.

Key Concepts

Constructing the prefix table

Set prefix[0] to zero. At index k, begin with j = prefix[k − 1].
While j > 0 and P[k] differs from P[j], replace j with prefix[j − 1].
If the letters agree, extend the border by one. Store the resulting j as prefix[k].

A border is both a prefix and a suffix; the two copies may overlap. For ABABAC the table is (0, 0, 1, 2, 3, 0). The prefix ABABA has border ABA of length 3, while the full pattern ABABAC has no nonempty border.

Why fallback preserves correctness

Suppose j letters have already matched. Any shorter candidate ending at the same text cursor must be a suffix of those matched letters and a prefix of P, hence a border of P[0..j). The longest such candidate is prefix[j − 1]. Its shorter candidates are reached through the same table. When j is zero and letters differ, advance i because no matched prefix can be reused.

A worked comparison trace

Search for ABABAC in ABABABAC. The first five comparisons match ABABA. At text index 5, B differs from pattern index 5, C. Instead of repeating the first five text letters, retain the length-3 border ABA. Keep i = 5 and set j = prefix[4] = 3. The same text B now matches pattern B at index 3. The following A and C complete a match starting at index 2. This search makes 9 character comparisons.

Overlaps and linear complexity

In AAAAA, pattern AAA occurs at indices 0, 1 and 2. After each full match, retain border AA of length 2 rather than discarding it. Each new A then completes another match. There are 5 search comparisons.

Prefix construction takes O(m) time. During search, i advances at most n times, and j can increase only when i advances. Each fallback strictly decreases j. The total work is therefore O(n), even though one text letter may be compared more than once. Preprocessing and search together take O(n + m) time and O(m) auxiliary space, excluding reported matches. This demonstration also retains a linear comparison history for replay. Its comparison counter excludes preprocessing.

Boundaries and input semantics

Empty text has no occurrences of a nonempty pattern. A longer pattern than the text is valid and cannot fully match.
This demonstration requires a nonempty pattern. Definitions that allow an empty pattern need a separate explicit convention.
Inputs are case-sensitive English letters, limited to 40 text letters and 16 pattern letters for readable replay. Unsupported or oversized input is rejected explicitly.
KMP can compare other alphabets or sequences when equality and index units are defined consistently; the English-letter restriction belongs to this demonstration.
Changing either string stops playback and clears old progress. Reset search retains the strings; Reset inputs restores the initial example.

Historical Context

Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt published Fast Pattern Matching in Strings in the SIAM Journal on Computing in 1977. The algorithm established a practical linear-time method for finding all occurrences of one pattern.

Real-world Applications

Text processing: Locate an exact phrase or token in a document without rescanning earlier text.
Streaming search: Retain the matched-prefix state across incoming chunks to detect a fixed pattern.
Sequence analysis: Find an exact DNA motif when approximate matching is not required.
Periodicity: Use proper borders to study repeated structure within a string.

Related Concepts

Rabin-Karp String Search: Uses rolling hashes and verifies candidate windows; KMP uses exact prefix structure.
Finite State Machine: The matched-prefix length acts as a state that changes with each input letter.
Suffix Array: Preprocesses the text for search queries, while KMP preprocesses one pattern.
Trie: Organizes shared prefixes of multiple strings; a KMP table describes borders of one pattern.

KMP String Matching