KMP - The Art of Efficient String Matching

String matching is one of those problems that seems trivial at first. You have a text, you have a pattern, you scan through the text looking for the pattern. What could go wrong? As it turns out, the naive approach hides a subtle inefficiency that becomes painful on large inputs. The Knuth-Morris-Pratt algorithm (KMP) solves this beautifully by exploiting a simple observation: when a mismatch occurs, we already know something about the characters we've just seen, and we can use that knowledge to avoid redundant comparisons.

I've always been drawn to algorithms that turn a clever observation into a significant performance gain. KMP is a textbook example of this. The idea behind it is both elegant and practical, and I wanted to implement it myself to make sure I truly understood the mechanics. I chose Rust for this implementation since it gives me the low-level control I enjoy while enforcing correctness at compile time. The code for this blog can be found here.

The Naive Approach

Let's start with what most of us would write instinctively. Given a text $T$ of length $n$ and a pattern $P$ of length $m$, we slide the pattern across the text one position at a time. At each position, we compare character by character:

Text:    A B A B C A B A B
Pattern: A B A B

Step 1: Compare T[0..3] with P[0..3] → match at index 0
Step 2: Shift pattern by 1, compare T[1..4] with P[0..3] → mismatch at P[0]
Step 3: Shift pattern by 1, compare T[2..5] with P[0..3] → partial match, mismatch at P[3]
...

The problem is clear: in the worst case, we compare each of the $n$ positions in the text against up to $m$ characters of the pattern, giving us $O(n \cdot m)$ time. For a text of 10 million characters and a pattern of 1000 characters, that's up to 10 billion comparisons. We can do better.

The Key Insight: Learning from Failure

Consider what happens when we're matching the pattern ABABC against a text and we've successfully matched ABAB but then encounter a mismatch at position 4 (the C). The naive approach would shift the pattern by one and start over. But think about what we already know: we've just matched ABAB. The suffix AB of what we matched is also a prefix of the pattern. This means we don't need to go all the way back. We can "slide" the pattern forward so that the prefix AB aligns with where that suffix was, and continue matching from there.

This is the core insight of KMP: when a mismatch occurs after matching some characters, the longest proper prefix of the matched portion that is also a suffix tells us exactly how far we can safely skip ahead.

The Prefix Table (Failure Function)

To exploit this insight, KMP precomputes a prefix table (also called the failure function) for the pattern. For each position $j$ in the pattern, the prefix table stores the length of the longest proper prefix of $P[0..j]$ that is also a suffix of $P[0..j]$.

Let's build this for the pattern ABABCABAB:

Index:        0  1  2  3  4  5  6  7  8
Pattern:      A  B  A  B  C  A  B  A  B
Prefix Table: 0  0  1  2  0  1  2  3  4

How do we read this? At index 7 the value is 3, meaning the longest proper prefix of ABABCABA that is also a suffix has length 3 (ABA). If we match up to index 7 and then hit a mismatch at index 8, we know we can fall back to index 3 in the pattern rather than starting over from scratch, because the prefix ABA is already aligned.

Building the Prefix Table

The construction itself is elegant. We use two pointers: $i$ tracks the length of the current matching prefix, and $j$ scans forward through the pattern starting at position 1.

• If $P[i] = P[j]$: the matching prefix extends. Set table[j] = i + 1, advance both.
• If $P[i] \neq P[j]$ and $i > 0$: fall back using the prefix table itself: i = table[i - 1].
• If $P[i] \neq P[j]$ and $i = 0$: no prefix matches. Set table[j] = 0, advance $j$.

The key detail is the fallback step. When a mismatch occurs, we don't reset $i$ to 0. Instead, we consult the prefix table at $i - 1$ to find the next longest prefix-suffix to try. This is precisely the same idea as the main search algorithm applied to the pattern against itself.

Let's trace through ABABCABAB:

j=1: P[0]=A vs P[1]=B → mismatch, i=0 → table[1]=0
j=2: P[0]=A vs P[2]=A → match → table[2]=1, i=1
j=3: P[1]=B vs P[3]=B → match → table[3]=2, i=2
j=4: P[2]=A vs P[4]=C → mismatch, i=2 → fall back: i=table[1]=0
     P[0]=A vs P[4]=C → mismatch, i=0 → table[4]=0
j=5: P[0]=A vs P[5]=A → match → table[5]=1, i=1
j=6: P[1]=B vs P[6]=B → match → table[6]=2, i=2
j=7: P[2]=A vs P[7]=A → match → table[7]=3, i=3
j=8: P[3]=B vs P[8]=B → match → table[8]=4, i=4

The runtime of this construction is $O(m)$. While it may look like the fallback could cause unbounded work, each fallback decreases $i$ and $i$ can only increase by 1 per iteration. Over the entire loop, the total number of fallbacks is bounded by $m$.

The Search Algorithm

With the prefix table in hand, the search algorithm follows the same structure. We maintain two pointers: $s$ for the text and $p$ for the pattern.

1. If $T[s] = P[p]$: both pointers advance.
2. If $p = m$ (full match): record the match at position $s - m$. Fall back: p = table[p - 1].
3. If $T[s] \neq P[p]$ and $p > 0$: fall back: p = table[p - 1].
4. If $T[s] \neq P[p]$ and $p = 0$: advance $s$.

Let's trace a search for pattern ABAB in text ABABCABAB:

s=0, p=0: A=A → s=1, p=1
s=1, p=1: B=B → s=2, p=2
s=2, p=2: A=A → s=3, p=3
s=3, p=3: B=B → s=4, p=4 → p=m! Match at index 0. Fall back: p=table[3]=2
s=4, p=2: C≠A → fall back: p=table[1]=0
s=4, p=0: C≠A → s=5
s=5, p=0: A=A → s=6, p=1
s=6, p=1: B=B → s=7, p=2
s=7, p=2: A=A → s=8, p=3
s=8, p=3: B=B → s=9, p=4 → p=m! Match at index 5. Fall back: p=table[3]=2

Result: matches at indices [0, 5].

Notice how after the first match, the algorithm doesn't start over from position 1. It falls back to $p=2$ because the suffix AB of the match is also a prefix of the pattern. This is where the speedup comes from.

Complexity Analysis

The search runs in $O(n)$ time. Combined with the $O(m)$ prefix table construction, the total is $O(n + m)$. The argument is the same amortization as for the prefix table: $p$ can only increase by 1 per iteration of the main loop, and each fallback decreases $p$, so the total number of fallbacks across the entire search is bounded by $n$.

This is a significant improvement over the $O(n \cdot m)$ naive approach. For our earlier example of 10 million characters with a 1000-character pattern, KMP guarantees at most ~11 million operations instead of up to 10 billion.

Rust Implementation

Here's how this looks in practice. The implementation uses Rust's type system to provide a clean API with proper error handling.

Core Types

pub struct Kmp {
    str: String,
    pattern: String,
}

Building the Prefix Table

fn build_prefix_table(&self, pat_as_vec: &Vec<char>) -> Vec<usize> {
    let mut prefix_table = vec![0; pat_as_vec.len()];
    prefix_table[0] = 0;

    let mut i = 0; // length of the current matching prefix
    let mut j = 1; // current position in the pattern

    while j < pat_as_vec.len() {
        if pat_as_vec[i] == pat_as_vec[j] {
            // Extend the matching prefix
            prefix_table[j] = i + 1;
            i += 1;
            j += 1;
        } else if i == 0 {
            // No prefix matches - move to next position
            prefix_table[j] = 0;
            j += 1;
        } else {
            // Fall back to the next longest prefix-suffix
            i = prefix_table[i - 1]
        }
    }
    prefix_table
}

The code maps directly to the algorithm we described. The three cases (match, mismatch at start, mismatch with fallback) are clearly delineated.

The Search

pub fn match_pattern(&self) -> Result<Vec<usize>, MatchErr> {
    if self.str.is_empty() {
        return Err(MatchErr::EmptyString);
    }

    if self.pattern.is_empty() {
        return Err(MatchErr::EmptyPattern);
    }

    let str_as_vec: Vec<char> = self.str.chars().collect();
    let pat_as_vec: Vec<char> = self.pattern.chars().collect();

    let prefix_table = self.build_prefix_table(&pat_as_vec);
    let mut result: Vec<usize> = Vec::new();

    let mut s_idx = 0;
    let mut p_idx = 0;

    while s_idx <= str_as_vec.len() {
        if p_idx == pat_as_vec.len() {
            result.push(s_idx - p_idx);
            p_idx = prefix_table[p_idx - 1]
        }

        if s_idx == str_as_vec.len() {
            break;
        }

        if str_as_vec[s_idx] == pat_as_vec[p_idx] {
            s_idx += 1;
            p_idx += 1;
        } else if p_idx == 0 {
            s_idx += 1;
        } else {
            p_idx = prefix_table[p_idx - 1]
        }
    }

    if result.is_empty() {
        Err(MatchErr::NoMatch)
    } else {
        Ok(result)
    }
}

A few design choices worth noting. The implementation converts strings to Vec<char> to handle Unicode correctly. Rust strings are UTF-8, and indexing by byte offset would break on multi-byte characters. By working with char values, the algorithm handles patterns like Japanese text naturally:

let kmp = Kmp::new("日本語で日本語".to_string(), "日本語".to_string());
assert_eq!(kmp.match_pattern().unwrap(), vec![0, 4]);

The API returns Result<Vec<usize>, MatchErr>, using Rust's error handling to distinguish between "no match found" and invalid inputs like empty strings.

Usage

let kmp = Kmp::new("ABABCABAB".to_string(), "AB".to_string());
let matches = kmp.match_pattern().unwrap();
// matches = [0, 2, 5, 7]

Where KMP Shows Up

KMP and its variants are used widely:

• Text editors and IDEs - "Find" and "Find and Replace" operations on large files.
• Bioinformatics - Searching for DNA subsequences within genomes, where both text and pattern can be very long.
• Network intrusion detection - Scanning packet payloads for known attack signatures at wire speed.
• Compilers and interpreters - Lexical analysis and tokenization.
• Log analysis - Searching through massive log files for specific error patterns.

While many modern implementations use more advanced algorithms like Aho-Corasick (for multiple patterns simultaneously) or Boyer-Moore (which can skip even more characters by examining the pattern from right to left), KMP remains foundational. Understanding KMP is often the gateway to understanding the entire family of linear-time string matching algorithms.

Conclusion

KMP is a beautiful example of how a single observation, that we can learn from our failures rather than discarding the work we've already done, leads to a fundamentally better algorithm. The prefix table captures the internal structure of the pattern, and the search exploits that structure to guarantee linear time. It's the kind of algorithm that, once you understand it, changes how you think about the relationship between preprocessing and search. Hopefully, this walkthrough has made the mechanics of KMP more accessible and has shown that there's real elegance hiding behind what might initially seem like a dry string matching algorithm.