KMP Pattern Matching Algorithm in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of KMP prefix table computation

What is the output array (prefix table) computed by the KMP algorithm for the pattern "ABABAC"?

DSA C++

int prefix[] = {0, 0, 0, 0, 0, 0};
// After running KMP prefix computation on "ABABAC"
// prefix array stores longest prefix suffix lengths
// What is the final prefix array?

A [0, 0, 1, 2, 3, 0]

B [0, 1, 0, 1, 2, 0]

C [0, 0, 1, 2, 0, 1]

D [0, 1, 2, 3, 4, 0]

💡 Hint

Remember prefix[i] stores the length of the longest proper prefix which is also suffix for substring pattern[0..i].

The prefix table for "ABABAC" is computed step-by-step. The longest prefix suffix lengths are [0,0,1,2,3,0].

❓ Predict Output

intermediate

KMP search output for pattern in text

Given the text "ABC ABCDAB ABCDABCDABDE" and pattern "ABCDABD", what is the starting index of the first match found by the KMP algorithm?

DSA C++

// Text: "ABC ABCDAB ABCDABCDABDE"
// Pattern: "ABCDABD"
// What is the index of the first occurrence of pattern in text using KMP?

A 10

B 15

C 8

D 5

💡 Hint

KMP finds the pattern starting at index 15 in the text.

The pattern "ABCDABD" first appears starting at index 15 in the text string.

🔧 Debug

advanced

Identify the bug in KMP prefix computation code snippet

What error will the following C++ code produce when computing the prefix table for pattern "AAACAAAA"?

DSA C++

int prefix[8] = {0};
int j = 0;
for (int i = 1; i < 8; i++) {
    while (j > 0 && pattern[i] != pattern[j]) {
        j = prefix[j - 1];
    }
    if (pattern[i] == pattern[j]) {
        j++;
    }
    prefix[i] = j;
}

A Logic error: prefix table values incorrect

B Runtime error: out of bounds access on prefix array

C Compilation error: 'pattern' not declared

D No error, prefix table computed correctly

💡 Hint

Check if all variables are declared and initialized properly.

The code snippet uses 'pattern' without declaring or initializing it, causing a compilation error.

❓ Predict Output

advanced

KMP algorithm behavior on repeated pattern

What is the output of the KMP search when searching for pattern "AAAA" in text "AAAAAAAA"? Output the starting indices of all matches found.

DSA C++

// Text: "AAAAAAAA"
// Pattern: "AAAA"
// Output all starting indices where pattern matches text using KMP

A [0, 4]

B [0, 2, 4]

C [0, 1, 2, 3, 4, 5]

D [0, 1, 2, 3, 4]

💡 Hint

Overlapping matches are found in KMP, so all valid starting indices are included.

The pattern "AAAA" appears starting at indices 0,1,2,3,4 in the text "AAAAAAAA" due to overlapping occurrences.

🧠 Conceptual

expert

Why does KMP algorithm run in linear time?

Which of the following best explains why the KMP algorithm runs in O(n + m) time, where n is the length of the text and m is the length of the pattern?

A Because it uses a prefix table to avoid re-examining characters in the text after a mismatch

B Because it checks every substring of the text against the pattern independently

C Because it uses recursion to divide the problem into smaller subproblems

D Because it sorts the pattern and text before searching

💡 Hint

Think about how KMP avoids repeating work on the text.

KMP uses the prefix table to skip unnecessary comparisons, ensuring each character in the text is examined at most once.

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