KMP Algorithm in C++ Explained: LPS Array, Dry Run, Implementation & Time Complexity

1. Introduction

String matching is a foundational problem in computer science: given a large body of text, how do we efficiently find a specific pattern within it? Whether you are searching for a keyword in a document, looking up a sequence in a massive DNA database, or utilizing the "Find" feature in your IDE, string matching algorithms are working behind the scenes.

The most intuitive approach is the Naive String Matching algorithm, which slides the pattern over the text one character at a time. However, this method is highly inefficient because it throws away valuable information. Every time a mismatch occurs, the naive approach resets its progress and starts over from the next character, leading to massive performance drops in the worst-case scenarios.

Enter the Knuth-Morris-Pratt (KMP) Algorithm. Discovered in 1977 by Donald Knuth, Vaughan Pratt, and James H. Morris, KMP revolutionized string searching by guaranteeing an optimal, linear-time $O(N + M)$ performance.

The secret weapon of KMP is its preprocessing step. By analyzing the pattern itself before the search even begins, KMP builds an LPS (Longest Prefix Suffix) array. This array acts as a roadmap, telling the algorithm exactly how far to shift the pattern when a mismatch occurs, completely avoiding unnecessary backward movements and repeated character comparisons.

2. Problem Statement

The String Matching Problem can be formally defined as follows:

Given:

1. A Text string (T) of length $N$.
2. A Pattern string (P) of length $M$.

Objective: Determine whether the Pattern exists as a contiguous substring within the Text. If it does, return the starting index of its first occurrence. If it does not exist, return a flag (usually -1) indicating no match.

Real-world Applications:

• Search engines: Finding query matches inside billions of indexed web pages.
• Text editors: The standard Ctrl+F (or Cmd+F) functionality.
• DNA sequence matching: Finding specific gene sequences within a massive genome.
• Antivirus software: Scanning files for known malware signatures.
• Log searching: Filtering through gigabytes of server logs for specific error codes.

3. Examples

Here are some standard inputs and their expected outputs.

4. Why Naive Search is Slow

To appreciate KMP, we must understand why the Naive Search fails. The naive algorithm aligns the pattern with the text and compares characters one by one. If a mismatch occurs, it shifts the pattern exactly one position to the right and starts comparing from the beginning of the pattern all over again.

A Visual Dry Run of Naive Search

Time Complexity:

In the worst-case scenario (like the one above), for every $N$ characters in the text, we compare $M$ characters in the pattern. This results in a time complexity of $O(N \times M)$. If you are searching a 10-million-character document for a 10,000-character sequence, this approach will hang your system.

5. Core Intuition of KMP

The fundamental flaw in the naive approach is repeated comparisons. When the naive algorithm mismatches, it "forgets" everything it just learned about the text.

KMP asks a brilliant question: When a mismatch occurs, can we use the characters we've already matched to avoid starting from scratch?

Reusing Matched Information

Suppose we matched the first 5 characters of a pattern, and the 6th character mismatches. Because we know exactly what those first 5 characters are (they are identical to the first 5 characters of our pattern), we can look at our pattern and figure out the next best alignment.

To do this, we need to understand the concepts of Prefixes and Suffixes.

• Prefix: Any substring that starts at the first character of a string.
• Proper Prefix: A prefix that is strictly shorter than the string itself.
• Suffix: Any substring that ends at the last character of a string.
• Proper Suffix: A suffix that is strictly shorter than the string itself.

The magic of KMP lies in finding the Longest Prefix that is also a Proper Suffix (LPS) for every substring of the pattern.

If we know the LPS, then when a mismatch occurs after matching $K$ characters, we know that the longest matching prefix and suffix of those $K$ characters is our new safe starting point. We can simply shift the pattern and resume comparing, without ever moving the text pointer backwards.

6. Understanding Prefix and Suffix

Let's break down prefixes and suffixes visually using the string ABABC.

String: ABABC

Proper Prefixes:

1. A
2. AB
3. ABA
4. ABAB

Proper Suffixes:

1. C
2. BC
3. ABC
4. BABC

Now, let's look at the substring ABAB (the first four characters of ABABC):

• Proper Prefixes of ABAB: A, AB, ABA
• Proper Suffixes of ABAB: B, AB, BAB

Notice that the string AB is both a proper prefix and a proper suffix of ABAB. Its length is 2. This means the LPS of ABAB is 2.

7. Building the LPS Array

The LPS array (often just called lps) has the same length as the pattern. The value lps[i] stores the length of the longest proper prefix that is also a suffix for the substring pattern[0...i].

Let's do a step-by-step dry run to build the LPS array for the pattern ABABC.

We use two pointers:

• len: Tracks the length of the previous longest prefix suffix. (Starts at 0)
• i: Iterates through the pattern from index 1 to $M-1$.

Initialization:

P = [A, B, A, B, C]

lps = [0, 0, 0, 0, 0] (Base case: lps[0] is always 0)

len = 0, i = 1

Step 1: i = 1

• Compare P[i] (B) with P[len] (A).
• Mismatch! (B != A)
• Since len == 0, we cannot backtrack. We set lps[1] = 0 and increment i.
• State: lps = [0, 0, 0, 0, 0], len = 0, i = 2

Step 2: i = 2

• Compare P[i] (A) with P[len] (A).
• Match! (A == A)
• Increment len to 1. Set lps[2] = 1. Increment i.
• State: lps = [0, 0, 1, 0, 0], len = 1, i = 3

Step 3: i = 3

• Compare P[i] (B) with P[len] (B - since len is 1, P[1] is 'B').
• Match! (B == B)
• Increment len to 2. Set lps[3] = 2. Increment i.
• State: lps = [0, 0, 1, 2, 0], len = 2, i = 4

Step 4: i = 4

• Compare P[i] (C) with P[len] (A - since len is 2, P[2] is 'A').
• Mismatch! (C != A)
• Because len > 0, we must backtrack. We look up the previous LPS value: len = lps[len - 1] = lps[1] = 0.
• We do not increment i yet.
• Retry Step 4: Compare P[4] (C) with P[0] (A).
• Mismatch! (C != A). Now len == 0, so we set lps[4] = 0 and increment i.
• Final Array: lps = [0, 0, 1, 2, 0]

LPS Array Visualizer

8. KMP Search Algorithm

With the LPS array constructed, searching the text becomes remarkably efficient. We maintain two pointers:

• i: Iterates through the Text (T).
• j: Iterates through the Pattern (P).

The Rules of KMP Search:

1. Character Match: If T[i] == P[j], we increment both i and j.
2. Pattern Found: If j == M (length of pattern), it means we found the entire pattern! We record the match index (i - j), and reset j using the LPS array (j = lps[j - 1]) to look for more occurrences.
3. Character Mismatch: If T[i] != P[j]:
   • If j > 0, we shift the pattern smartly. We set j = lps[j - 1]. Crucially, we do not increment i here. We test the same text character against the newly aligned pattern character.
   • If j == 0, we simply move to the next text character by incrementing i.

Because the pointer i never moves backwards, KMP completely eliminates the repeated comparisons that plague the Naive approach.

9. Complete Dry Run

Let's walk through the main algorithm using: Text (T): ABABDABACDABABCABAB Pattern (P): ABABCABAB

First, KMP computes the LPS array for ABABCABAB: lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]

10. C++ Implementation

Here is the complete, production-ready implementation of the KMP algorithm in modern C++. It is cleanly divided into the preprocessing function and the search function.

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

using namespace std;

// Function to compute the Longest Prefix Suffix (LPS) array
vector<int> computeLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0); // Initialize LPS array with 0s
    
    int len = 0; // Length of the previous longest prefix suffix
    int i = 1;   // i starts from 1 because lps[0] is always 0
    
    // Loop calculates lps[i] for i = 1 to m-1
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            // Mismatch after some matches
            if (len != 0) {
                // Backtrack len to the previous known LPS
                // We DO NOT increment i here.
                len = lps[len - 1];
            } else {
                // No prefix matched, lps is 0
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// Function to perform KMP string matching
// Returns all starting indices where the pattern is found
vector<int> KMPSearch(const string& text, const string& pattern) {
    vector<int> matches;
    int n = text.length();
    int m = pattern.length();
    
    // Edge cases
    if (m == 0) return matches;
    if (n < m) return matches;
    
    // Preprocess pattern to get LPS array
    vector<int> lps = computeLPS(pattern);
    
    int i = 0; // index for text
    int j = 0; // index for pattern
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            // Pattern found!
            matches.push_back(i - j);
            
            // Look for next match using LPS to skip characters
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            // Mismatch after j matches
            if (j != 0) {
                // Do not match lps[0..lps[j-1]] characters, 
                // they will definitely match.
                j = lps[j - 1];
            } else {
                // If j is 0, we simply move to the next character in text
                i++;
            }
        }
    }
    return matches;
}

int main() {
    string text = "ABABDABACDABABCABAB";
    string pattern = "ABABCABAB";
    
    vector<int> occurrences = KMPSearch(text, pattern);
    
    if (occurrences.empty()) {
        cout << "Pattern not found in the text." << endl;
    } else {
        cout << "Pattern found at indices: ";
        for (int index : occurrences) {
            cout << index << " ";
        }
        cout << endl;
    }
    return 0;
}

11. Complexity Analysis

Time Complexity: $O(N + M)$

• Preprocessing (computeLPS): Generating the LPS array takes time proportional to the length of the pattern. Even though there is a while loop inside the main loop, the variable len is bounded. The total operations are at most $2M$. Hence, the preprocessing takes $O(M)$ time.
• Searching (KMPSearch): We iterate through the text of length $N$. The index i never decreases. Although j can decrease when backtracking via the LPS array, j can never be decreased more times than it has been incremented. The maximum number of operations is $2N$. Hence, searching takes $O(N)$ time.
• Total Time Complexity: $O(N) + O(M) = O(N + M)$. This is strictly linear and optimally fast.

Space Complexity: $O(M)$

KMP requires an external array (the LPS array) of the exact same length as the pattern. Thus, the space complexity is exactly $O(M)$, where $M$ is the length of the pattern.

13. Advantages

1. Guaranteed Linear Time: Unlike Naive or Rabin-Karp which can degrade to $O(N \times M)$ under worst-case inputs, KMP fundamentally guarantees $O(N + M)$ performance.
2. No Backtracking in Text: The text pointer i only ever moves forward. This makes KMP exceptional for processing streaming data (like network packets or endless logs) where you cannot easily "rewind" the data stream.
3. Suitable for Huge Texts: When parsing through gigabytes of text looking for a small sequence, avoiding repeated character reads saves massive amounts of CPU and I/O time.
4. Interview Favorite: Because it proves a deep understanding of arrays, state machines, and dynamic programming concepts, KMP is a highly respected algorithm in top-tier tech interviews.

14. Disadvantages

1. Difficult to Understand: As you may have gathered, the logic behind the LPS array and the dual-pointer backtracking is famously counter-intuitive for beginners.
2. Hard to Implement Correctly: An off-by-one error when setting j = lps[j-1] or failing to properly check len != 0 will cause infinite loops or skipped matches.
3. Requires Preprocessing & Space: For extremely short patterns, allocating memory for the $O(M)$ array and running the preprocessing loop can actually be slower than just using a highly optimized hardware-level Naive search.

15. Applications

The theoretical robustness of KMP allows it to power several critical systems:

• Google Search / Web Crawlers: Finding exact quote matches within newly scraped websites efficiently.
• VS Code Find / grep: Under the hood, advanced text editors utilize algorithms derived from KMP and Boyer-Moore to execute instant searches.
• Bioinformatics: DNA is heavily repetitive (GATTACA...). KMP flawlessly prevents worst-case scenarios when searching for gene markers.
• Intrusion Detection Systems: Scanning incoming network packet payloads for specific malware signatures on the fly (since KMP doesn't need to rewind the stream).
• Compiler Design: Lexical analyzers use similar state-machine concepts to match tokens in source code.
• Plagiarism Detection: Matching document fragments against massive databases of existing work.
• Text Analytics: High-frequency keyword extraction in natural language processing pipelines.

16. Interview Questions

If you are preparing for coding interviews, be ready to answer these conceptual questions about KMP:

Q: Why is KMP better than Naive Search?

A: Naive search discards matched character information upon a mismatch, forcing it to rewind the text pointer. KMP uses the LPS array to remember matched characters, ensuring the text pointer only moves forward, resulting in linear $O(N + M)$ time compared to the naive $O(N \times M)$.

Q: What exactly is the LPS array?

A: LPS stands for Longest Prefix Suffix. For every substring of the pattern ending at index i, lps[i] stores the length of the longest proper prefix of that substring that is also a suffix. It dictates how far to shift the pattern upon a mismatch.

Q: Why doesn't KMP move the text pointer backwards?

A: Because any information before the current text pointer i has already been perfectly matched against the pattern. The LPS array tells us what the new alignment should be without needing to re-read those previous text characters.

Q: Can KMP find multiple occurrences?

A: Yes. When a match is found (i.e., j == M), we simply record the index, and then update j = lps[j-1] to simulate a mismatch and force the algorithm to look for the next occurrence.

Q: What is the difference between KMP and Rabin-Karp?

A: KMP uses string prefix/suffix properties and state transitions to avoid re-evaluating text. Rabin-Karp uses a rolling hash function to compare strings mathematically. Rabin-Karp is easier to extend to 2D matching or multiple-pattern matching, but suffers from hash collisions.

Q: What is the difference between KMP and the Z Algorithm?

A: Both are $O(N + M)$. KMP builds an array of size $M$ (the pattern), whereas the Z Algorithm concatenates the pattern and text (Pattern + "$" + Text) and builds an array of size $N + M + 1$. Z Algorithm is generally easier to code, but KMP uses less auxiliary memory.

Q: When should KMP be preferred?

A: KMP should be strictly preferred when the text is very large, the text contains highly repetitive sequences, and you only need to search for a single, specific pattern.

video link: