Knuth–Morris–Pratt (KMP)

Precompute a failure (prefix) function so you never rescan matched characters after a mismatch.

Why Not Restart from Scratch?

After a mismatch at pattern position j, the naive algorithm shifts the pattern by one and compares from j = 0 again. But the last j characters of T already matched P[0..j−1]. KMP exploits this overlap: some prefix of P might equal a proper suffix of P[0..j−1], so the next alignment can skip characters we already know match.

The Prefix Function π (failure function)

Define π[q] as the length of the longest proper prefix of P[0..q] that is also a suffix of P[0..q].

Example: for P = "ababaca", π helps after a mismatch tell you how far to slide P without backing up in T — the text index only advances forward.

Compute π in O(m) with a single left-to-right scan that reuses earlier π values (similar idea to the matcher itself).

Matching with KMP

Maintain text index i and pattern index q. For each character T[i]:

While q > 0 and T[i] ≠ P[q], set q = π[q−1] (fall back along the border chain).
If T[i] = P[q], increment q.
If q = m, report a match ending at i, then set q = π[m−1] to find overlapping matches.

Key property: T is never scanned backward; each comparison either advances i or shrinks q, yielding O(n) matching time after O(m) preprocessing.

Pseudocode

Standard CLRS-style prefix-function build, then the linear-time scanner.

1COMPUTE-PREFIX-FUNCTION(P, m)
2  pi[0] = 0
3  k = 0
4  for q = 2 to m
5    while k > 0 and P[k+1] ≠ P[q]
6      k = pi[k]
7    if P[k+1] = P[q]
8      k = k + 1
9    pi[q] = k
10  return pi
11
12KMP-MATCHER(T, n, P, m)
13  pi = COMPUTE-PREFIX-FUNCTION(P, m)
14  q = 0
15  occurrences = []
16  for i = 1 to n
17    while q > 0 and P[q+1] ≠ T[i]
18      q = pi[q]
19    if P[q+1] = T[i]
20      q = q + 1
21    if q = m
22      occurrences.append(i - m)
23      q = pi[m]
24  return occurrences

Complexity

Build π: O(m) time, O(m) space.

Match: O(n) time; total O(n + m). Space: O(m) for π.

Unlike Rabin–Karp, there is no hash collision — KMP is exact and worst-case optimal for this single-pattern online model.

Complexity Analysis

Time Complexity

O(n + m)

Space Complexity

O(m) for the prefix function

Linear worst-case; no hashing

Growth Rate Comparison