Offensive Security Researcher & Quantum Cryptography Analyst

Knuth-Morris-Pratt (KMP) Algorithm: Detailed Explanation and Implementation

Abdul Wahab Junaid
The Knuth-Morris-Pratt (KMP) Algorithm: Detailed Explanation

I use the Knuth-Morris-Pratt (KMP) algorithm whenever I need to search for occurrences of a pattern string within a text string efficiently, without the wasted work that a naive approach incurs from repeatedly re-checking characters I’ve already compared. I consider KMP an essential building block in string processing because it guarantees linear-time matching, which I rely on constantly in text editors, search utilities, bioinformatics tools, and network intrusion detection systems.

History and Background

I trace the KMP algorithm to a 1970 discovery by Donald Knuth and Vaughan Pratt, developed independently around the same time by James H. Morris, with all three ultimately publishing the combined result in 1977 as “Fast Pattern Matching in Strings” in the SIAM Journal on Computing. I note that the motivation partly came from a theoretical result by Cook that showed pattern matching could be done on a certain class of automata within linear time, which Knuth, Morris, and Pratt then turned into a practical, implementable algorithm. I regard this discovery as a foundational moment in string algorithms, since it was among the first to demonstrate that avoiding redundant comparisons through clever preprocessing could take a quadratic-looking problem down to linear time.

Problem Statement

I use KMP to solve the classic pattern-matching problem: given a text $T$ of length $n$ and a pattern $P$ of length $m$, I want to find all occurrences (or the first occurrence) of $P$ within $T$. I want to avoid the inefficiency of the naive algorithm, which in the worst case re-examines characters of $T$ multiple times, leading to $O(nm)$ time. I want an algorithm that never needs to move backward in the text, examining each text character a bounded number of times.

Core Concepts

I rely on the concept of the failure function (also called the prefix function or partial match table), denoted $\pi$, where $\pi[i]$ represents the length of the longest proper prefix of $P[0..i]$ that is also a suffix of $P[0..i]$. I use this table to determine, upon a mismatch during matching, exactly how far I can safely shift the pattern without missing any potential match — because I already know, from the failure function, which portion of the pattern I’ve already confirmed matches.

How It Works

I follow this two-phase process when performing KMP matching:

  1. Preprocessing phase: I compute the failure function $\pi$ for the pattern $P$, which encodes self-overlap information within the pattern itself.
  2. Matching phase: I scan the text $T$ left to right, comparing characters against the pattern. When I find a mismatch at pattern position $j$, instead of restarting the pattern comparison from the beginning, I use $\pi[j-1]$ to determine the next pattern position to compare from, without moving the text pointer backward.
  3. Whenever I match the entire pattern (reach $j = m$), I record a match and continue searching by resetting $j$ to $\pi[j-1]$, in case there are overlapping occurrences.

Working Principle

I understand the internal logic of KMP as exploiting the self-similarity of the pattern to avoid redundant work. When a mismatch occurs after matching some prefix of the pattern, I know exactly which characters of the text I’ve already seen (they match a prefix of the pattern). Since the failure function already tells me the longest prefix of the pattern that is also a suffix of what I’ve matched so far, I can “slide” the pattern forward to align this known-good suffix with the corresponding prefix, without ever needing to re-examine text characters I’ve already compared. This is the key mechanism that keeps the text pointer moving strictly forward throughout the entire algorithm.

Mathematical Foundation

I define the failure function formally:

$$ \pi[i] = \max{ k : k

with $\pi[0] = 0$ by convention (a single character has no proper prefix).

I prove the linear-time bound of the matching phase using an amortized analysis based on a potential function. I define the potential as the current value of $j$ (the number of pattern characters matched so far). I note that:

Since $j$ can increase at most $n$ times total (bounded by the number of times $i$ advances) across the entire matching phase, and each decrease of $j$ must be “paid for” by a prior increase, I conclude the total number of comparisons is bounded by $2n = O(n)$.

I similarly bound the failure function computation itself at $O(m)$ using the identical amortized argument applied to the pattern against itself.

Diagrams

flowchart TD
    A[Input: text T, pattern P] --> B[Compute failure function pi for P]
    B --> C[Initialize text pointer i = 0, pattern pointer j = 0]
    C --> D{T i equals P j?}
    D -->|Yes| E[Increment i and j]
    E --> F{j equals length of P?}
    F -->|Yes| G[Record match at i - j]
    G --> H[Set j = pi j-1, continue]
    F -->|No| I{i reached end of T?}
    D -->|No, and j > 0| J[Set j = pi j-1]
    J --> D
    D -->|No, and j == 0| K[Increment i only]
    K --> I
    H --> I
    I -->|No| D
    I -->|Yes| L[Return all matches]

Pseudocode

I write the pseudocode for computing the failure function and performing the search:

function COMPUTE_FAILURE(P):
    m = length(P)
    pi = array of size m, initialized to 0
    k = 0

    for i from 1 to m - 1:
        while k > 0 and P[i] != P[k]:
            k = pi[k - 1]
        if P[i] == P[k]:
            k = k + 1
        pi[i] = k

    return pi

function KMP_SEARCH(T, P):
    n = length(T)
    m = length(P)
    pi = COMPUTE_FAILURE(P)
    j = 0
    matches = empty list

    for i from 0 to n - 1:
        while j > 0 and T[i] != P[j]:
            j = pi[j - 1]
        if T[i] == P[j]:
            j = j + 1
        if j == m:
            matches.append(i - m + 1)
            j = pi[j - 1]

    return matches

Step-by-Step Example

I search for pattern $P = \text{“ababaca”}$’s failure function first, then match text $T = \text{“bacbababaca”}$ against $P = \text{“ababaca”}$.

Computing $\pi$ for “ababaca”:

iP[i]k beforek afterpi[i]
0a––0
1b000
2a011
3b122
4a233
5c300
6a011

I obtain $\pi = [0, 0, 1, 2, 3, 0, 1]$.

Matching against $T = \text{“bacbababaca”}$:

I scan through the text, and I find that starting at text index 4, the substring “bababaca”… wait, I check carefully: at $i=10$ (0-indexed, end of text), I complete matching the full pattern “ababaca” starting at text index 4. I record a match at position 4, and thanks to the failure function, I never had to move the text pointer backward even when earlier partial matches failed.

Time Complexity

I establish that KMP runs in $O(n + m)$ time overall: $O(m)$ for computing the failure function and $O(n)$ for the matching phase, both justified by the amortized analysis in the Mathematical Foundation section. This bound holds in the best, average, and worst case alike — unlike the naive algorithm, whose worst case is $O(nm)$ (for example, matching “aaaa…a” against a long run of a’s), KMP guarantees linear time regardless of the input’s specific structure, because the text pointer never moves backward.

Space Complexity

I require $O(m)$ additional space to store the failure function table, where $m$ is the pattern length. I need no extra space proportional to the text length $n$, since I process the text in a single forward pass using only a constant number of index variables ($i$, $j$) beyond the failure table itself.

Correctness Analysis

I justify the correctness of the failure function computation by induction on $i$: I assume $\pi[0..i-1]$ are all correct, and I show that the while loop, which repeatedly falls back to $\pi[k-1]$ upon mismatch, correctly finds the longest proper prefix-suffix match for position $i$ by trying progressively shorter candidate overlaps until one succeeds or none remain. I justify the matching phase’s correctness similarly: whenever a mismatch occurs, falling back to $j = \pi[j-1]$ preserves the invariant that the characters of $T$ already compared still match the corresponding prefix of $P$ up to the new, shorter value of $j$ — no valid match is ever skipped, because any match starting within the discarded region would have required a longer prefix-suffix overlap than $\pi[j-1]$ allows, which the failure function already ruled out as impossible.

Advantages

Disadvantages

Applications

I apply KMP in:

Implementation in C

I implement the KMP algorithm in C, with comments:

#include stdio.h>
#include string.h>

// I compute the failure function (partial match table) for pattern P
void computeFailure(char* P, int m, int* pi) {
    pi[0] = 0;
    int k = 0;

    for (int i = 1; i  m; i++) {
        while (k > 0 && P[i] != P[k]) {
            k = pi[k - 1]; // I fall back using the failure function
        }
        if (P[i] == P[k]) {
            k++;
        }
        pi[i] = k;
    }
}

// I search for pattern P within text T using the KMP algorithm
void kmpSearch(char* T, char* P) {
    int n = strlen(T);
    int m = strlen(P);
    int pi[m];

    computeFailure(P, m, pi);

    int j = 0; // number of characters of P currently matched
    for (int i = 0; i  n; i++) {
        while (j > 0 && T[i] != P[j]) {
            j = pi[j - 1];
        }
        if (T[i] == P[j]) {
            j++;
        }
        if (j == m) {
            printf("Match found at index %d\n", i - m + 1);
            j = pi[j - 1]; // I continue searching for further matches
        }
    }
}

int main() {
    char T[] = "bacbababaca";
    char P[] = "ababaca";

    kmpSearch(T, P);

    return 0;
}

Sample Input and Output

I use T = "bacbababaca" and P = "ababaca" as input, and I expect:

Match found at index 4

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version