Knuth-Morris-Pratt Algorithm (String Matching)

Definition

Knuth–Morris–Pratt Algorithm (String Matching)

The Knuth–Morris–Pratt algorithm solves the string matching problem by using repeated structure in the pattern to retain successful comparisons after a mismatch. Given text $T$ of length $n$ and pattern $P$ of length $m$, it returns all zero-based occurrence positions:

$$\{s\in \{0,\dots ,n-m\}:T[s..s+m-1]=P\}.$$

It first computes the pattern’s prefix function, then scans the text without moving the text index backwards. The running time is $O(n+m+1)$, including empty inputs, with $O(m+1)$ auxiliary space excluding the output. An empty pattern occurs at all $n+1$ text boundaries.

Discovering the Algorithm

A Mismatch Does Not Erase the Matches

Suppose we want to find this pattern. The numbers above the characters are zero-based indices.

Here is the text we will search. For now, let us simply place the pattern at its beginning and compare from left to right.

The first five comparisons succeed. Then the text has b where the pattern expects c. This occurrence has failed—but we have learned that the first five text characters are ababa.

The naïve approach moves the pattern one position right and starts again. Start $1$ fails immediately. Start $2$ is more interesting: its first three comparisons succeed, spelling aba.

Those three text characters were already checked. Can we know that they match the new alignment without reading them again?

Set the text aside for a moment. The part of the pattern that matched was ababa. Its ending aba is exactly its beginning aba. Orange marks these equal parts in the diagram below.

Now combine two facts. The successful comparisons told us that the text ends with the matched ababa. The pattern tells us that this ending aba equals its beginning. Therefore those text characters already match the beginning of the shifted pattern.

The reusable part is a border: both a prefix and a suffix of the matched string. We want the longest proper border. Keeping the whole string would leave the pattern at the alignment that just failed.

Turn the Repeated Structure into a Jump

We will need this information after different numbers of successful comparisons. Rather than discover the border each time, store its length for every pattern prefix. This table is the prefix function: $\pi (q)$ gives the longest proper border length of $P[\mathrm{0..}q]$, with zero for the empty border.

Suppose $L$ characters have matched. Their indices are $0,\dots ,L-1$: a length of five ends at index four. That is why we read $k=\pi (L-1)$.

Here the table takes the ending index $4$ and returns the retained length $3$. Reading $\pi (5)$ instead would ask about ababac, including the c that failed to match.

Where should the pattern move? The retained aba occupies the last three positions of the five-character match. Its beginning is two positions after the old start. In general, discard $L-k$ positions and retain $k$:

Let $i$ be the next text index. Before the move, $L$ characters extend backwards from $i$; afterwards, only $k$ do. Thus

$$\begin{array}{rl}\text{old start}& =i-L,\\ \text{new start}& =i-k,\\ \text{shift}& =(i-k)-(i-L)=L-k.\end{array}$$

Bring the text back. Move the pattern by $5-3=2$, retain the orange aba, and retry the pending text character against $P[3]$. Nothing requires us to move backwards in the text.

This comparison succeeds: both characters are b. We now have four matched characters and can advance the text index. The move has avoided both the impossible start $1$ and the three repeated comparisons at start $2$.

But what if the retry had failed? We would need a shorter suffix that is still a pattern prefix. Such candidates are precisely the nested borders of the part we retained. The same lookup works again: replace the current length $L$ by $\pi (L-1)$.

At fixed text index $i=5$, the lengths $5\to 3\to 1\to 0$ give starts $0\to 2\to 4\to 5$. Starts $1$ and $3$ cannot work: baba and ba do not equal the corresponding pattern prefixes. Each arrow is taken only after another mismatch; a successful comparison stops the fallback.

At length zero, try $P[0]$. If even that fails, there is nothing left to retain: advance the text index. So the search needs just a text position $i$ and a matched length $L$—the pattern’s start is implicit in $i-L$.

There is one more place where we should keep a border: after a complete match. If $m=|P|$ characters have matched through text index $i$, report start $i-m+1$. Then retain $\pi (m-1)$ characters, since the next occurrence may share the end of this one.

Build the Table with the Same Idea

We have derived the search assuming the table is available. Can we also build that table without repeatedly comparing the same pattern characters?

Suppose the table is known through index $q-1$. Its last value $k=\pi (q-1)$ gives the longest border of the prefix seen so far. To extend that border by one character, compare $P[k]$ with the new character $P[q]$.

If they agree, store $k+1$. If they disagree, try the next shorter border, $k\leftarrow \pi (k-1)$, against the same $P[q]$. This is the search mechanism again, but entirely inside the pattern.

In the diagram, the new c cannot extend any candidate, so $\pi (5)=0$. At the next index, a agrees with $P[0]$, giving $\pi (6)=1$. Start with $\pi (0)=0$ and proceed left to right to obtain the entire table.

We now have both phases: first learn where each pattern prefix repeats at its own end; then use that information to retain matches while scanning the text. The two loops below use the same fallback rule.

Pseudocode

Slices use inclusive endpoints; an empty range or slice contains no elements. and short-circuits. The array access pi[q] denotes $\pi (q)$.

compute_pi(P):
    m := |P|
    pi := array of m zeros
    k := 0
    for q := 1 to m - 1:
        while k > 0 and P[k] != P[q]:
            k := pi[k - 1]
        if P[k] == P[q]:
            k := k + 1
        pi[q] := k
    return pi
 
kmp_search(T, P):
    n := |T|
    m := |P|
    if m == 0:
        return [0, ..., n]
 
    pi := compute_pi(P)
    occurrences := []
    L := 0
    for i := 0 to n - 1:
        while L > 0 and P[L] != T[i]:
            L := pi[L - 1]
        if P[L] == T[i]:
            L := L + 1
        if L == m:
            append i - m + 1 to occurrences
            L := pi[m - 1]
    return occurrences

There is no explicit shift variable. A fallback changes $L$ without consuming $T[i]$; the outer loop consumes that character only after the retries finish.

Correctness

Fallback Enumerates Exactly the Shorter Candidates

Border candidates

Suppose $A=P[\mathrm{0..}L-1]$ is a suffix of the consumed text. For $0\le k<L$,

$$P[\mathrm{0..}k-1]\text{ is a suffix of the consumed text}⟺P[\mathrm{0..}k-1]\text{ is a border of }A.$$

Consequently, repeated lookups $L\leftarrow \pi (L-1)$ enumerate all shorter suffix matches in decreasing length.

Proof

The last $k$ characters of the consumed text lie inside its suffix $A$. They are therefore exactly the last $k$ characters of $A$.

Matching them with $P[\mathrm{0..}k-1]$ is equivalent to matching the first and last $k$ characters of $A$. This is the border condition.

The longest proper border is given by $\pi (L-1)$. By nesting and transitivity, every shorter border is a border of that border, and conversely. Repeating the lookup skips no border and strictly decreases the length until zero.

The Prefix Table Is Correct

Correct prefix values

compute_pi(P) returns the prefix function of $P$.

Proof

Base: a one-character prefix has only the empty proper border, so $\pi (0)=0$. For empty $P$, the returned array is empty.

Induction: before processing $q\ge 1$, earlier table entries are correct and $k=\pi (q-1)$.

A non-empty proper border of $P[\mathrm{0..}q]$ of length $r$ must satisfy

$$\begin{array}{rl}P[\mathrm{0..}r-1]& =P[q-r+\mathrm{1..}q],\\ P[\mathrm{0..}r-2]& =P[q-r+\mathrm{1..}q-1],\\ P[r-1]& =P[q].\end{array}$$

Thus its first $r-1$ characters form a proper border of $P[\mathrm{0..}q-1]$, and its last character extends that border. Conversely, any such extension gives a proper border of $P[\mathrm{0..}q]$.

The fallback lemma enumerates all candidate lengths $r-1$ from largest to smallest. The first successful comparison gives the longest extension; if none succeeds, zero is correct. Hence the stored $\pi (q)$ is correct, completing the induction.

The Search Reports Exactly All Occurrences

For $m>0$, define the candidate lengths before processing text index $i$:

$$C_i=\{\ell \in \{0,\dots ,m-1\}:P[\mathrm{0..}\ell -1]\text{ is a suffix of }T[\mathrm{0..}i-1]\}.$$

The invariant at the start of each outer iteration is $L=\max C_i$. It deliberately excludes length $m$: complete matches ending before $i$ have already been reported.

Exact occurrence positions

kmp_search(T, P) returns all and only the positions where $P$ occurs in $T$, in increasing order, including overlapping occurrences.

Proof

Initialisation: before $i=0$, the consumed text is empty and $C_0=\{0\}$. Thus $L=0$ satisfies the invariant.

Extension: a non-empty prefix match of length $r\le m$ ending at $i$ exists exactly when

$$r-1\in C_i\text{and}P[r-1]=T[i].$$

Removing its last character proves necessity; appending the matching character proves sufficiency.

Fallback: starting at $\max C_i$, the lemma enumerates all candidates in decreasing order. A mismatch rejects only the current candidate. The first successful comparison therefore gives the greatest length $r$ ending at $i$; if all fail, that length is zero.

Reporting: if $r=m$, then $T[i-m+\mathrm{1..}i]=P$, so the reported start is valid. Conversely, any occurrence ending at $i$ gives $r=m$ and is reported. No endpoint is omitted because the outer loop visits every text character.

Restoring the invariant: if $r<m$, retain $L=r$. If $r=m$, the longest shorter suffix match is the longest proper border of $P$, so set $L=\pi (m-1)$. Either way, $L=\max C_{i+1}$.

Termination: each fallback strictly decreases a positive length; each outer iteration consumes one text character. All iterations finish, establishing the result. If $m=0$, the explicit branch returns exactly the $n+1$ boundaries.

Complexity

A text character may be compared more than once during fallback. Linear time follows from counting changes of the matched length, not from claiming one comparison per character.

During search, $L$ increases by at most one per text character. Each fallback decreases it by at least one; resets after full matches also decrease it. Since $L$ starts at zero and stays non-negative,

$$\begin{array}{rl}\#\text{fallbacks}& \le \text{total decrease of }L,\\ \text{total decrease of }L& \le \text{total increase of }L\le n.\end{array}$$

The remaining work is constant per text character and occurrence. The same argument with $k$ gives linear prefix-table construction.

Phase	Time	Auxiliary space
Build the prefix table	$O(m+1)$	$O(m+1)$
Scan the text	$O(n+1)$	$O(1)$ beyond the table
Total	$O(n+m+1)$	$O(m+1)$ excluding output

For $z$ occurrences, the output list uses $O(z+1)$ space. Character equality is assumed to take constant time. The algorithm handles exact contiguous matching; wildcard or approximate matching requires different rules.

Examples

A complete scan with one fallback

For $P=\mathrm{ababaca}$ and $T=\mathrm{abababaca}$, the prepared table is $[0,0,1,2,3,0,1]$.

Text index $i$	$T[i]$	$L$ before	Action	$L$ after, including reset
0	a	0	Match $P[0]$	1
1	b	1	Match $P[1]$	2
2	a	2	Match $P[2]$	3
3	b	3	Match $P[3]$	4
4	a	4	Match $P[4]$	5
5	b	5	Fail at $P[5]$; retain $\pi (4)=3$; match $P[3]$	4
6	a	4	Match $P[4]$	5
7	c	5	Match $P[5]$	6
8	a	6	Reach $7$; report $8-7+1=2$; retain $\pi (6)=1$	1

The returned list is $[2]$.

Overlapping matches

For $P=\mathrm{aba}$ and $T=\mathrm{ababa}$, the returned list is $[0,2]$. After the first match, retaining $\pi (2)=1$ preserves the shared a at text position $2$.

Empty and impossible patterns

For $P=\epsilon$ and $T=\mathrm{abc}$, return $[0,1,2,3]$. For non-empty $P$ and empty $T$, or for $|P|>|T|$, return $[]$.