KMP Pattern Matching Algorithm in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the prefix array with zeros.

DSA C++

int prefix[n] = { [1] };

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing prefix array with ones or negative values.

Not initializing the prefix array at all.

The prefix array should be initialized with zeros to start building the longest prefix suffix values.

2fill in blank

medium

Complete the code to update the prefix array when characters match.

DSA C++

if (pattern[i] == pattern[j]) {
    j++;
    prefix[i] = [1];
    i++;
}

Drag options to blanks, or click blank then click option'

Ai

B0

Cprefix[j]

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning prefix[i] to i instead of j.

Assigning zero instead of the updated prefix length.

When characters match, prefix[i] is set to j, the length of the current longest prefix suffix.

3fill in blank

hard

Fix the error in the while loop condition for building the prefix array.

DSA C++

while (i < n) {
    if (pattern[i] == pattern[j]) {
        j++;
        prefix[i] = j;
        i++;
    } else {
        if ([1] != 0) {
            j = prefix[j - 1];
        } else {
            prefix[i] = 0;
            i++;
        }
    }
}

Drag options to blanks, or click blank then click option'

Aj

Bi

Cprefix[i]

Dprefix[j]

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of j in the condition.

Using prefix[i] or prefix[j] incorrectly.

The condition checks if j is not zero to fallback to the previous longest prefix suffix.

4fill in blank

hard

Fill both blanks to correctly update indices during the search phase.

DSA C++

while (i < n) {
    if (text[i] == pattern[j]) {
        i++;
        j = [1];
    } else {
        if (j != 0) {
            j = [2];
        } else {
            i++;
        }
    }
}

Drag options to blanks, or click blank then click option'

Aj + 1

Bprefix[j - 1]

Cj - 1

Dprefix[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Not incrementing j on match.

Incorrect fallback index on mismatch.

When characters match, j increments by 1; when mismatch occurs and j is not zero, j falls back to prefix[j-1].

5fill in blank

hard

Fill all three blanks to correctly detect pattern matches and reset j.

DSA C++

if (j == [1]) {
    result.push_back(i - j);
    j = [2];
}

// Build prefix array
int prefix[n] = {0};
int i = 1, j = 0;
while (i < [3]) {
    // prefix array logic
}

Drag options to blanks, or click blank then click option'

Am

Bprefix[j - 1]

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong length variables for comparisons.

Not resetting j correctly after a match.

j equals pattern length m means a full match; reset j to prefix[j-1]; prefix array is built for pattern length n.

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