Why KMP Pattern Matching Algorithm in DSA C++?

The Big Idea

What if you could find a needle in a haystack without digging through the whole pile again and again?

The Scenario

Imagine you have a huge book and you want to find every place where a certain sentence appears. You start reading from the beginning each time you find a mismatch, going back and forth slowly.

The Problem

This manual search is very slow and tiring because you keep re-reading parts of the book again and again. It wastes time and can easily cause mistakes if you lose track.

The Solution

The KMP algorithm helps by remembering where to continue searching after a mismatch, so you never go back to the start. It uses a smart table to skip unnecessary checks and find the pattern quickly.

Before vs After

✗ Before

for (int i = 0; i <= text_length - pattern_length; i++) {
  int j = 0;
  while (j < pattern_length && text[i + j] == pattern[j]) {
    j++;
  }
  if (j == pattern_length) return i;
}

✓ After

int i = 0, j = 0;
while (i < text_length) {
  if (text[i] == pattern[j]) {
    i++; j++;
    if (j == pattern_length) return i - j;
  } else if (j > 0) {
    j = lps[j - 1];
  } else {
    i++;
  }
}

What It Enables

KMP enables fast and efficient searching of patterns in large texts without unnecessary repetition.

Real Life Example

Searching for a specific word or phrase in a large document or DNA sequence quickly and accurately.

Key Takeaways

KMP avoids re-checking characters by using a precomputed table.

It speeds up pattern searching in big texts.

It is more efficient than simple brute force search.

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