KMP String Matching — LPS Off-by-One Bug in Production

KMP is one of those algorithms that every senior engineer has encountered in a 1am incident. You're processing a 500MB log file looking for a pattern — maybe a specific error signature or a token format — and your naive substr search is burning through CPU. KMP is the fix, and understanding why it works is what separates engineers who reach for the right tool versus engineers who reach for regex and hope for the best.

Published in 1977 by Knuth, Morris, and Pratt, KMP solves string pattern matching in O(n+m) time — guaranteed, not amortised, not average-case. It works by never re-examining a character in the text. Once the text pointer moves right, it never goes left. This single invariant is why the algorithm runs in linear time regardless of what adversarial pattern you throw at it. The mechanism that enforces this invariant is the LPS array — and once you truly understand LPS, you'll see it hidden inside Z-algorithm, Aho-Corasick, and even suffix arrays.

How KMP Works — Plain English and Algorithm

The naive string search checks every position in the text and compares the pattern character by character — O(n*m) worst case. KMP (Knuth-Morris-Pratt) is faster because it never re-examines characters it has already matched. When a mismatch occurs, KMP uses a precomputed table to skip ahead intelligently instead of restarting from scratch.

The key insight: when a mismatch occurs at pattern[j], the substring pattern[0..j-1] was already matched. The 'failure function' (or LPS array — Longest Proper Prefix which is also Suffix) tells us the longest proper prefix of pattern[0..j-1] that is also a suffix. We can restart matching from that prefix instead of from the beginning.

Step 1 — Build the LPS (failure function) array for the pattern: 1. lps[0] = 0 always. 2. Use two pointers: len=0 (length of previous longest prefix-suffix), i=1. 3. If pattern[i] == pattern[len]: lps[i] = len+1, increment both i and len. 4. Else if len > 0: len = lps[len-1] (try a shorter prefix — do NOT increment i). 5. Else: lps[i] = 0, increment i.

Step 2 — Search the text using the LPS array: 1. Use two pointers: i (text index), j (pattern index), both start at 0. 2. If text[i] == pattern[j]: increment both i and j. 3. If j == len(pattern): match found at index i-j. Set j = lps[j-1]. 4. Else if i < len(text) and text[i] != pattern[j]: - If j > 0: j = lps[j-1] (skip via failure function, do NOT move i). - Else: increment i.

Time complexity: O(n + m) where n = text length, m = pattern length. The LPS build is O(m) and the search is O(n).

Visual LPS Table Construction

The LPS array is built by walking through the pattern and determining the longest proper prefix that is also a suffix for each prefix of the pattern. The algorithm maintains a length variable that tracks the length of the previous longest prefix-suffix. At each step, the table shows the current state of the LPS array and the positions of pattern[i] and pattern[len]. This visual breaks down the construction for the pattern 'ABABCAB' (length 7) step by step.

The diagram below shows the LPS array evolving after each comparison.

Worked Example — KMP Search for 'ABCAB' in 'ABABCABCABAB'

Pattern: ABCAB Text: ABABCABCABAB

Step 1 — Build LPS for pattern 'ABCAB': i=0: lps[0]=0 (always) i=1: pattern[1]='B' vs pattern[0]='A'. No match. lps[1]=0. i=2: pattern[2]='C' vs pattern[0]='A'. No match. lps[2]=0. i=3: pattern[3]='A' vs pattern[0]='A'. Match! lps[3]=1, len=1. i=4: pattern[4]='B' vs pattern[1]='B'. Match! lps[4]=2, len=2. LPS = [0, 0, 0, 1, 2]

Step 2 — Search (i=text index, j=pattern index): i=0,j=0: text[0]='A'==pattern[0]='A'. i=1,j=1. i=1,j=1: text[1]='B'==pattern[1]='B'. i=2,j=2. i=2,j=2: text[2]='A'!=pattern[2]='C'. j=lps[1]=0. i=2,j=0: text[2]='A'==pattern[0]='A'. i=3,j=1. i=3,j=1: text[3]='B'==pattern[1]='B'. i=4,j=2. i=4,j=2: text[4]='C'==pattern[2]='C'. i=5,j=3. i=5,j=3: text[5]='A'==pattern[3]='A'. i=6,j=4. i=6,j=4: text[6]='B'==pattern[4]='B'. j==5==len(pattern)! MATCH at index i-j=6-5=1... wait, i-j=6-5=1? No: i=7 after increment, j=5 equals pattern length. Match at i-j=7-5=2. j=lps[4]=2. Continue search from i=7,j=2... i=7,j=2: text[7]='C'==pattern[2]='C'. i=8,j=3. i=8,j=3: text[8]='A'==pattern[3]='A'. i=9,j=4. i=9,j=4: text[9]='B'==pattern[4]='B'. Match at i-j=10-5=5. j=lps[4]=2.

Matches found at indices 2 and 5 in the text.

Notice that after finding a match, KMP uses lps[j-1] to slide the pattern forward by the right amount — it does not restart from the beginning of the pattern.

KMP Implementation

The two-function structure (build_lps and kmp_search) matches the two-phase algorithm exactly. Study build_lps carefully — the len backtrack using lps[len-1] is the subtlest part.

def build_lps(pattern):
    m   = len(pattern)
    lps = [0] * m
    length = 0  # length of previous longest prefix-suffix
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length > 0:
            length = lps[length - 1]  # try shorter prefix
            # do NOT increment i here
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0: return []
    lps = build_lps(pattern)
    matches = []
    i = j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1; j += 1
        if j == m:
            matches.append(i - j)  # match at this index
            j = lps[j - 1]
        elif i < n and text[i] != pattern[j]:
            if j > 0:
                j = lps[j - 1]
            else:
                i += 1
    return matches

text    = 'ABABCABCABAB'
pattern = 'ABCAB'
print('LPS:', build_lps(pattern))
print('Matches at indices:', kmp_search(text, pattern))

C++ Implementation

The C++ implementation of KMP mirrors the Python version but requires careful handling of array indices and the std::vector container. The LPS construction and search functions are split similarly. Key differences: C++ uses size_t for indices, and the LPS array is built with a while loop that may not increment i in every iteration. The search function returns a vector of match positions. Below is a complete, production-ready C++ implementation that follows the same logic as the Python reference.

#include <vector>
#include <string>
#include <iostream>

std::vector<int> build_lps(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> lps(m, 0);
    int len = 0;  // length of previous longest prefix-suffix
    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else if (len > 0) {
            len = lps[len - 1];  // backtrack without incrementing i
        } else {
            lps[i] = 0;
            i++;
        }
    }
    return lps;
}

std::vector<int> kmp_search(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();
    if (m == 0) return {};
    std::vector<int> lps = build_lps(pattern);
    std::vector<int> matches;
    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++; j++;
        }
        if (j == m) {
            matches.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j > 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
    return matches;
}

int main() {
    std::string text = "ABABCABCABAB";
    std::string pattern = "ABCAB";
    std::vector<int> lps = build_lps(pattern);
    std::cout << "LPS: ";
    for (int v : lps) std::cout << v << " ";
    std::cout << std::endl;
    std::vector<int> matches = kmp_search(text, pattern);
    std::cout << "Matches at indices: ";
    for (int idx : matches) std::cout << idx << " ";
    std::cout << std::endl;
    return 0;
}

Common KMP Mistakes and How to Debug Them

Even experienced engineers slip up on KMP's fallback logic. The algorithm has three high-risk areas: the LPS backbuilding loop, the mismatch fallback in search, and the match-continuation handler.

1. Off-by-one in LPS fallback: When len is not equal to 0 and pattern[i] != pattern[len], you must set len = lps[len-1]. Using lps[len] or lps[len-2] produces wrong values that cascade into missed matches.
2. Confusing j and i in search: After a mismatch, you must NOT increment i when j > 0. This is the most common infinite-loop trigger. Only increment i when j == 0.
3. After a match, setting j = 0 instead of j = lps[j-1]: This kills overlap detection. If your pattern is 'AA' and text is 'AAA', you'll miss the match at index 1.
4. Forgetting that LPS lengths are always < j: lps[j-1] is always less than j. If your fallback index ever equals or exceeds j, you have a bug in LPS construction.

KMP Variants, Complexity, and When to Use Alternatives

KMP is not always the fastest string matching algorithm for every scenario. Here's how it compares:

• Boyer-Moore: Usually faster for large alphabets because it can skip more characters per mismatch (bad character and good suffix heuristics). Worst-case O(n*m) but rarely hits it.
• Rabin-Karp: Uses rolling hash. Good for multiple pattern search (plagiarism detection), but O(n*m) worst-case from hash collisions.
• Aho-Corasick: Builds a finite automaton from multiple patterns simultaneously. Ideal for virus signature detection or filtering many keywords.
• Z-algorithm: Computes an array Z[i] = longest substring starting at i that matches prefix. Can be used to find all matches in O(n+m) with simpler code than KMP.

KMP remains the best choice when you need guaranteed linear time and low overhead for a single pattern search. It's also the foundation for understanding more complex string algorithms.

Formal O(n) Complexity Proof

The KMP search algorithm guarantees O(n) time because the outer while loop runs at most n times where n is the text length. The key invariant: the text index i never decreases; it either increments (when a character matches or when j=0 and mismatch occurs) or stays the same (when j>0 and a mismatch occurs, causing j to fallback). However, each time j falls back, j decreases by at least 1, and j can only increase when i increments. Since j is bounded by m (pattern length), the total number of fallbacks across the entire search is also bounded by the total number of i increments, which is at most n. Therefore the total number of operations in the search loop is O(n).

More formally: let the search loop have two types of operations: - Type A: i increases by 1 (and j may increase at most 1). This can happen at most n times. - Type B: j decreases by at least 1 (via lps[j-1]). Since j starts at 0 and never exceeds m, and each increase of j (in Type A) is paired with an increase in i, the total number of Type B operations is at most the total number of Type A operations, i.e., at most n. Hence total operations ≤ 2n = O(n).

The LPS construction has an analogous proof: the pointer i only moves forward (at most m times), and the variable len only decreases when backtracking. Each backtrack reduces len by at least 1, and each increase of len is paired with an increment of i. So total backtrack steps ≤ m, giving O(m) for the build phase. Thus overall O(n+m).

String Period and Compression with KMP

One powerful application of the LPS (prefix function) is computing the smallest period of a string. The period of a string s is the smallest integer p such that s[i] = s[i+p] for all i where i+p < |s|. This is equivalent to saying that s is made up of repetitions of a substring of length p. Using the LPS array (or equivalently the prefix function), the smallest period of s is |s| - LPS[|s|-1] if |s| % (|s| - LPS[|s|-1]) == 0, otherwise the string is not periodic.

More concretely: let π denote the prefix function (same as LPS but defined for the whole string, not just prefixes). Then the length of the smallest period is n - π[n-1] if n % (n - π[n-1]) == 0. For example, for s = "ABABAB", n=6, LPS last value = 4 (since "ABAB" is prefix-suffix), period = 6-4=2. Indeed "AB" repeated 3 times.

This property allows string compression: a periodic string can be stored as a base substring and a repeat count, reducing memory. It also helps in finding repeated substrings in DNA sequences or log patterns. In competitive programming, you can solve problems like "Find the smallest period of a string" or "Check if a string can be formed by repeating a substring" using this technique.

Practice Problems

Solidify your understanding of KMP by solving these problems that leverage the algorithm and its variants. They range from direct application to more creative uses of the prefix function. Attempt them in order of difficulty and test against edge cases like overlapping patterns.

Frequently Asked Questions