KMP Pattern Matching Algorithm in DSA C++ - Build from Scratch

KMP Pattern Matching Algorithm

📖 Scenario: You are building a text search tool that quickly finds all occurrences of a small pattern inside a large text. This is useful in searching documents, DNA sequences, or logs.

🎯 Goal: Implement the Knuth-Morris-Pratt (KMP) algorithm to efficiently find all starting positions of a given pattern inside a given text.

📋 What You'll Learn

Create a function to build the longest prefix suffix (LPS) array for the pattern

Create a function to use the LPS array to find all pattern occurrences in the text

Print all starting indices where the pattern is found in the text

💡 Why This Matters

🌍 Real World

Text search is used in editors, search engines, and bioinformatics to quickly find patterns in large data.

💼 Career

Understanding KMP algorithm is important for software engineers working on search features, data processing, and algorithm optimization.

1

Create the text and pattern strings

Create two std::string variables called text and pattern with these exact values: text = "ABABDABACDABABCABAB" and pattern = "ABABCABAB".

DSA C++

# Create the text and pattern strings
// Your code here

Hint

Use std::string to store the text and pattern exactly as given.

2

Create the LPS array builder function

Add a function called computeLPSArray that takes const std::string &pattern and int lps[] as parameters. Inside it, create variables int length = 0 and int i = 1. Use a while loop with condition i < pattern.length() to fill the lps array with the longest prefix suffix values for the pattern.

DSA C++

#include 
#include 

void computeLPSArray(const std::string &pattern, int lps[]) {
    // Your code here
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    return 0;
}

Hint

Follow the KMP LPS array building logic: compare characters, update length, and fill lps.

3

Create the KMP search function

Add a function called KMPsearch that takes const std::string &text, const std::string &pattern, and int lps[]. Use two indices int i = 0 for text and int j = 0 for pattern. Use a while loop with condition i < text.length() to find all occurrences of the pattern in the text using the LPS array. Print each starting index of a match with std::cout.

DSA C++

#include 
#include 

void computeLPSArray(const std::string &pattern, int lps[]) {
    int length = 0;
    int i = 1;
    lps[0] = 0;
    while (i < (int)pattern.length()) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPsearch(const std::string &text, const std::string &pattern, int lps[]) {
    // Your code here
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    return 0;
}

Hint

Use two pointers i and j to scan text and pattern. Use the LPS array to skip characters on mismatch.

4

Call functions and print pattern occurrences

In main(), create an integer array lps of size pattern.length(). Call computeLPSArray(pattern, lps) to fill it. Then call KMPsearch(text, pattern, lps) to print all starting indices where the pattern is found in the text.

DSA C++

#include 
#include 

void computeLPSArray(const std::string &pattern, int lps[]) {
    int length = 0;
    int i = 1;
    lps[0] = 0;
    while (i < (int)pattern.length()) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPsearch(const std::string &text, const std::string &pattern, int lps[]) {
    int i = 0; // index for text
    int j = 0; // index for pattern
    while (i < (int)text.length()) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == (int)pattern.length()) {
            std::cout << "Pattern found at index " << i - j << std::endl;
            j = lps[j - 1];
        } else if (i < (int)text.length() && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    int lps[pattern.length()];
    // Your code here
    return 0;
}

Hint

Remember to create the lps array, call computeLPSArray, then call KMPsearch to print matches.

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) algorithm in pattern matching?

easy

A. To find occurrences of a pattern in a text efficiently without rechecking characters

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the number of vowels in the text

Solution

1. Step 1: Understand KMP's goal

   KMP algorithm is designed to search for a pattern inside a text efficiently.

2. Step 2: Identify how it works

   It avoids rechecking characters by using a prefix table to skip unnecessary comparisons.

3. Final Answer:

   To find occurrences of a pattern in a text efficiently without rechecking characters -> Option A

4. Quick Check:

   KMP purpose = efficient pattern search [OK]

Hint: KMP skips repeated checks using prefix info [OK]

Common Mistakes:

• Thinking KMP sorts or modifies the text
• Confusing KMP with simple substring search
• Assuming KMP counts characters or vowels

2. Which of the following is the correct way to declare the prefix (lps) array in C++ for KMP algorithm?

easy

A. int lps[pattern_length];

B. int* lps = new int[pattern_length];

C. int lps = new int[pattern_length];

D. int lps[] = pattern_length;

Solution

1. Step 1: Understand dynamic array allocation in C++

   To create an array dynamically, use pointer with new keyword: int* lps = new int[size];

2. Step 2: Check options

   int* lps = new int[pattern_length]; correctly uses pointer and new to allocate array of given length.

3. Final Answer:

   int* lps = new int[pattern_length]; -> Option B

4. Quick Check:

   Dynamic array = int* lps = new int[size]; [OK]

Hint: Use int* with new[] for dynamic arrays in C++ [OK]

Common Mistakes:

• Using int lps = new int[] (wrong type)
• Declaring fixed size without initialization
• Incorrect array syntax like int lps[] = size

3. What will be the output of the following code snippet that uses KMP to find pattern occurrences?

std::string text = "ababcabcabababd";
std::string pattern = "ababd";
std::vector<int> result = kmpSearch(text, pattern);
for(int pos : result) std::cout << pos << " ";

Assuming kmpSearch returns all starting indices of pattern in text.

medium

A. 10

B. 0 5 10

C. 5 10

D. No output

Solution

1. Step 1: Identify pattern occurrences in text

   Check where "ababd" appears in "ababcabcabababd". It appears starting at index 10 only.

2. Step 2: Confirm output format

   kmpSearch returns vector of indices; printing them separated by space outputs "10 ".

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Pattern found at index 10 only [OK]

Hint: Scan text for exact pattern start index [OK]

Common Mistakes:

• Assuming multiple matches without checking text
• Confusing substring indices
• Printing no output if pattern not found

4. Consider this buggy code snippet for computing the LPS array in KMP:

void computeLPSArray(string pat, int M, int* lps) {
  int len = 0;
  lps[0] = 0;
  int i = 1;
  while (i < M) {
    if (pat[i] == pat[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len != 0) {
        len = lps[len];  // Bug here
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
}

What is the bug and how to fix it?

medium

A. Replace while with for loop

B. Initialize len to 1 instead of 0

C. Remove else block completely

D. Change len = lps[len]; to len = lps[len - 1];

Solution

1. Step 1: Identify incorrect index in LPS update

   When mismatch occurs and len != 0, len should be updated to lps[len-1], not lps[len].

2. Step 2: Correct the assignment

   Change len = lps[len]; to len = lps[len - 1]; to avoid out-of-bound and logical error.

3. Final Answer:

   Change len = lps[len]; to len = lps[len - 1]; -> Option D

4. Quick Check:

   LPS update uses len-1 index [OK]

Hint: Use len-1 index when updating len in LPS [OK]

Common Mistakes:

• Using len index directly causes wrong LPS values
• Changing loop type unnecessarily
• Removing else block breaks logic

5. Given a text and multiple patterns, which approach best uses KMP to find all patterns efficiently?

hard

A. Run KMP separately for each pattern on the text

B. Concatenate all patterns and run KMP once

C. Build a trie of patterns and run Aho-Corasick algorithm

D. Use KMP only on the longest pattern

Solution

1. Step 1: Understand KMP's limitation

   KMP efficiently finds one pattern in text but running it repeatedly for many patterns is inefficient.

2. Step 2: Identify better multi-pattern method

   Building a trie and using Aho-Corasick algorithm finds all patterns simultaneously efficiently.

3. Final Answer:

   Build a trie of patterns and run Aho-Corasick algorithm -> Option C

4. Quick Check:

   Multi-pattern search = Aho-Corasick [OK]

Hint: Use Aho-Corasick for multiple patterns [OK]

Common Mistakes:

• Running KMP repeatedly wastes time
• Concatenating patterns confuses matching
• Ignoring specialized multi-pattern algorithms