Knuth Morris Pratt algorithm: Definition & Examples

The Knuth Morris Pratt algorithm (KMP) finds exact, contiguous occurrences of a fixed pattern in a sequence. After a mismatch, it uses the pattern’s overlaps to keep part of what already matched, so the scan never needs to go back to an earlier input position. A quant developer can use it to locate a fixed sequence of event types in a replay log, even when the sequence crosses a read-buffer boundary. Knuth, Morris and Pratt’s original paper

The mismatch at index 5

Search the text ABABABAC for the pattern ABABAC, using zero-based indices. Starting at index 0, the first five symbols match as ABABA. The text then has B at index 5, where the pattern expects C.

For a match to start inside the five symbols just checked, the remaining suffix of ABABA must also be a prefix of the pattern. The longest such overlap is ABA. It occupies text indices 2 through 4, so the next viable start is index 2. KMP retains those three matches and compares the same text B to the pattern’s B at index 3. The final A and C match in turn. The first and only match begins at index 2 and ends at index 7.

Text ABABABAC and pattern ABABAC first align at index 0. At text index 5, B differs from C after five matches. Shifting the pattern to start at index 2 preserves ABA at text indices 2 through 4, so the same B can be tested against pattern index 3.

The pattern shifts two positions while the text cursor stays at index 5. The blue bracket marks the three symbols that already match in the new alignment.

Build the table from the pattern

A border here means a proper prefix that is also a suffix of the same string. Proper excludes the whole string. The prefix table stores

\pi_i

, the length of the longest border of the pattern prefix ending at index

i

, or zero if it has no nonempty border.

Pattern prefix	A	AB	ABA	ABAB	ABABA	ABABAC
Longest border length	0	0	1	2	3	0

Build the table from left to right. Try to extend the previous prefix’s longest border by one symbol. If it cannot extend, try its own longest border and repeat. Any shorter viable border of the previous prefix is itself a border of the longer one, so following this chain checks the candidates in descending length. For ABABAC, the border ABA would need B to extend, and so would the shorter border A. Starting from the empty border would need A. The appended C rules out all three extensions. Misra’s notes on computing borders

During the scan, let $j$ be the number of pattern symbols matched immediately before the current text position. When the next comparison fails and $j>0$ , replace $j$ with $\pi_{j-1}$ and retry the current symbol. In the example, $\pi_4=3$ is the relevant entry because five symbols matched. When $j=0$ and the comparison fails, move to the next input symbol. After reporting a full match, fall back to the full pattern’s border length before continuing so an overlapping occurrence can still be found.

What one pass buys you

Assume a nonempty pattern of length

m

, an input of length

n

and constant-time symbol comparisons and table lookups. Building the table takes

O(m)

time and the scan takes

O(n)

, for

O(m+n)

total time and

O(m)

auxiliary storage excluding the input and reported positions. A single input symbol can trigger several fallbacks. Across the whole scan, however, each successful symbol comparison raises the matched length by one, and each fallback lowers it by at least one. The decreases are bounded by the increases, which gives the linear time complexity. The table-building pass uses the same argument. Misra’s scan and preprocessing analysis

For a replay, carry the matched length and absolute input position across chunks of the same ordered stream. When a feed gap or session boundary breaks the intended sequence, reset the matched length so the search cannot report a match across that break. The SelfMadeQuant lesson on market data shows how sequence numbers and receipt times determine what belongs in a replay. The full lesson requires membership. Trades, Quotes and Market State

A match certifies equality of the encoded symbols in order. If an extra or substituted event is allowed, the task calls for a similarity rule such as edit distance.

Sources

Donald E. Knuth, James H. Morris Jr. and Vaughan R. Pratt (1977). Fast Pattern Matching in Strings. The original analysis of pattern shifts, preprocessing and linear running time.
Jayadev Misra (2017). Knuth-Morris-Pratt Algorithm. The scan invariant, nested borders, and the linear-time construction of the border table.

The mismatch at index 5

Build the table from the pattern

What one pass buys you

Sources

Related terms

Edit distance

Time complexity