Offensive Security Researcher & Quantum Cryptography Analyst

KMP (Knuth-Morris-Pratt) Algorithm: Working, Explanation, and Pattern Matching

Abdul Wahab Junaid
KMP algorithm and working of this algorithm

When I first ran into the problem of searching for a pattern inside a large body of text, my instinct was to just slide the pattern over the text one character at a time and compare. It works, but I quickly realized how wasteful it is when the pattern has repeating structure. The Knuth-Morris-Pratt algorithm, or KMP, is the classical answer to this inefficiency. It lets me search for a substring inside a string in linear time, without ever moving backward in the main text. I find that property — never re-reading a character of the text — to be the single most elegant thing about this algorithm, and it’s why KMP remains a staple in compilers, text editors, DNA sequence analysis, and intrusion detection systems.

History and Background

I trace this algorithm back to 1970, when Donald Knuth and Vaughan Pratt worked out the theoretical idea, and James H. Morris independently arrived at essentially the same approach while working on text editors. The three published their joint result in 1977 in the paper “Fast Pattern Matching in Strings.” What strikes me about the history is that Morris’s motivation was very practical — he wanted a fast way to search inside a text editor — while Knuth and Pratt approached it from a more theoretical angle related to a question about whether a certain class of languages could be recognized quickly. The convergence of a practical need and a theoretical proof into a single clean algorithm is part of why I find KMP such a satisfying piece of computer science history.

Problem Statement

I want to find every occurrence (or the first occurrence) of a pattern string P of length m inside a text string T of length n. The brute-force way to do this costs me up to O(n*m) comparisons in the worst case, because after a mismatch I throw away all the information I’ve already gathered and restart the pattern from its beginning at the next position in the text. KMP is designed to solve exactly this inefficiency: it asks how I can avoid re-examining text characters I’ve already matched, by using the structure of the pattern itself to know how far I can safely skip.

Core Concepts

Before I can explain how KMP works, I need to define a few terms I rely on throughout:

How It Works

I break KMP into two clear phases:

  1. Preprocessing phase — I build the LPS (Longest Proper Prefix which is also Suffix) array for the pattern P. This is a one-time cost of O(m).
  2. Searching phase — I scan the text T once, using the LPS array to decide, on a mismatch, how far to shift the pattern without re-checking characters of the text I’ve already compared.

During searching, I keep two pointers: i for the text and j for the pattern.

Working Principle

The internal logic rests on a simple but powerful observation: if I’ve already matched j characters of the pattern before hitting a mismatch, I know exactly what those j characters of text were — they were P[0..j-1]. So instead of asking “does the pattern match starting at the next text position,” which brute force does blindly, I ask “given that I already know these characters, what is the longest prefix of the pattern that I don’t have to re-verify.” That answer is precisely LPS[j-1]. This is why the text pointer i never needs to backtrack — all the information needed to decide the next alignment is already encoded in the pattern’s own self-similarity.

Mathematical Foundation

The LPS array is formally defined as:

$$ LPS[i] = \max{k : k < i+1,\ P[0..k-1] = P[i-k+1..i]} $$

for i = 0, 1, ..., m-1, with LPS[0] = 0 by convention.

The total work done across both phases is bounded because the pointer i in the text never decreases, and the pointer j can decrease at most as many times as it has increased. Formally, if I let the number of increments of i be at most n, and note that j increases at most once per increment of i, then the total decrements of j (each corresponding to an O(1) failure-function lookup) are also bounded by n. This gives:

$$ T(n, m) = O(n) + O(m) $$

for the combined preprocessing and searching phases.

Diagrams

flowchart TD
    A["Start: i = 0, j = 0"] --> B{"T[i] equals P[j]?"}

    B -- Yes --> C["Increment i and j"]
    C --> D{"Have all pattern characters matched?"}

    D -- Yes --> E["Record match and update j using LPS"]
    E --> F{"Are characters remaining in the text?"}

    D -- No --> F

    F -- Yes --> B
    F -- No --> J["End"]

    B -- No --> G{"Is j greater than 0?"}

    G -- Yes --> H["Update j using LPS"]
    H --> F

    G -- No --> I["Increment i"]
    I --> F

Pseudocode

function buildLPS(P, m):
    LPS[0] = 0
    length = 0
    i = 1
    while i < m:
        if P[i] == P[length]:
            length = length + 1
            LPS[i] = length
            i = i + 1
        else:
            if length != 0:
                length = LPS[length - 1]
            else:
                LPS[i] = 0
                i = i + 1
    return LPS

function KMPSearch(T, P):
    n = length(T)
    m = length(P)
    LPS = buildLPS(P, m)
    i = 0
    j = 0
    matches = []
    while i < n:
        if T[i] == P[j]:
            i = i + 1
            j = j + 1
            if j == m:
                matches.append(i - j)
                j = LPS[j - 1]
        else:
            if j != 0:
                j = LPS[j - 1]
            else:
                i = i + 1
    return matches

Step-by-Step Example

Let me trace through a concrete case. Suppose:

Step 1 — Build the LPS array for ABABCABAB:

Index012345678
CharABABCABAB
LPS001201234

Step 2 — Search:

I start comparing T and P from the left. The first few characters ABAB match, then at position 4 the text has D while the pattern expects C, so I fail at j = 4. Instead of restarting j at 0, I look up LPS[3] = 2, meaning the prefix AB of the pattern is already known to match, so I resume comparison from j = 2 without moving the text pointer backward. I continue this process across the text and eventually find a full match of ABABCABAB starting at index 10 of the text.

Time Complexity

Space Complexity

I need O(m) extra space to store the LPS array. The search phase itself uses only a constant number of extra variables (i, j), so the total auxiliary space is O(m), independent of the size of the text.

Correctness Analysis

The correctness of KMP rests on proving that whenever I shift the pattern using j = LPS[j-1] after a mismatch, I never skip over a valid match. This is true because any alignment I skip would require the skipped portion of the pattern to match a portion of text that I’ve already proven (through the matched prefix) cannot equal that pattern prefix — by definition, LPS[j-1] is the longest border, so any shift smaller than what LPS dictates would necessarily reproduce a match I’ve already ruled out. Because the LPS array captures all self-overlaps of the pattern, no potential match position is ever missed, and the algorithm is provably correct by induction on the matched length.

Advantages

Disadvantages

Applications

I’ve seen KMP applied in:

Implementation in C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Build the LPS (failure function) array for the pattern */
void buildLPS(char *pattern, int m, int *lps) {
    int length = 0;   /* length of the previous longest prefix-suffix */
    lps[0] = 0;       /* LPS[0] is always 0 */
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                /* fall back using the LPS array itself, no i increment */
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

/* Search for pattern in text, printing every match position */
void KMPSearch(char *text, char *pattern) {
    int n = strlen(text);
    int m = strlen(pattern);

    int *lps = (int *)malloc(m * sizeof(int));
    buildLPS(pattern, m, lps);

    int i = 0; /* index for text */
    int j = 0; /* index for pattern */

    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == m) {
                printf("Pattern found at index %d\n", i - j);
                j = lps[j - 1]; /* look for the next match */
            }
        } else if (j != 0) {
            j = lps[j - 1];   /* skip using precomputed failure links */
        } else {
            i++;
        }
    }

    free(lps);
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";

    KMPSearch(text, pattern);
    return 0;
}

Sample Input and Output

Input:

Text: ABABDABACDABABCABAB
Pattern: ABABCABAB

Output:

Pattern found at index 10

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version