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[] ComputePrefixTable(string pattern) {
    int[] prefix = new int[pattern.Length];
    int j = 0;
    for (int i = 1; i < pattern.Length; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefix[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
            prefix[i] = j;
        }
    }
    return prefix;
}

var result = ComputePrefixTable("ABABAC");
Console.WriteLine(string.Join(",", result));

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

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

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

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

💡 Hint

Remember the prefix table stores the length of the longest proper prefix which is also a suffix for each substring.

The prefix table for "ABABAC" is computed step-by-step. The last value is 0 because 'C' does not continue the prefix pattern.

❓ Predict Output

intermediate

KMP pattern search output

What is the output of the following KMP search code when searching for pattern "ABABC" in text "ABABABCABABC"?

DSA C#

List<int> KMPSearch(string text, string pattern) {
    int[] prefix = ComputePrefixTable(pattern);
    List<int> result = new List<int>();
    int j = 0;
    for (int i = 0; i < text.Length; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = prefix[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == pattern.Length) {
            result.Add(i - j + 1);
            j = prefix[j - 1];
        }
    }
    return result;
}

var positions = KMPSearch("ABABABCABABC", "ABABC");
Console.WriteLine(string.Join(",", positions));

A [3,8]

B [0,5]

C [1,6]

D [2,7]

💡 Hint

Check where the pattern fully matches in the text.

The pattern "ABABC" appears starting at indices 2 and 7 in the text.

🔧 Debug

advanced

Identify the error in prefix table computation

What error will the following code produce when computing the prefix table for pattern "AABAACAABAA"?

DSA C#

int[] ComputePrefixTable(string pattern) {
    int[] prefix = new int[pattern.Length];
    int j = 0;
    for (int i = 1; i < pattern.Length; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefix[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
            prefix[i] = j;
        }
    }
    return prefix;
}

var prefixTable = ComputePrefixTable("AABAACAABAA");

A IndexOutOfRangeException

B NullReferenceException

C No error, returns correct prefix table

D StackOverflowException

💡 Hint

Check the loop boundary conditions and array indexing.

The loop uses i <= pattern.Length which causes index out of range when accessing pattern[i].

🧠 Conceptual

advanced

Why does KMP use the prefix table?

What is the main purpose of the prefix table in the KMP algorithm?

A To store the indices of all pattern matches in the text

B To count the total number of pattern occurrences in the text

C To store the longest prefix which is also a suffix to avoid rechecking characters

D To reverse the pattern for backward search

💡 Hint

Think about how KMP avoids repeating comparisons.

The prefix table helps KMP skip unnecessary comparisons by remembering how far to jump back in the pattern.

🚀 Application

expert

KMP search with overlapping patterns

Given the text "AAAAA" and pattern "AAA", how many times does the KMP algorithm find the pattern in the text?

A 4

B 3

C 1

D 2

💡 Hint

Consider overlapping occurrences of the pattern.

The pattern "AAA" appears starting at indices 0, 1, and 2 in the text "AAAAA".

Practice

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

easy

A. To find occurrences of a pattern string within a text efficiently

B. To sort an array of numbers in ascending order

C. To reverse a string in linear time

D. To calculate the factorial of a number recursively

Solution

1. Step 1: Understand the goal of KMP

   KMP is designed to search for a pattern inside a larger text efficiently without rechecking characters unnecessarily.

2. Step 2: Compare with other options

   Sorting, reversing strings, and calculating factorials are unrelated to pattern searching.

3. Final Answer:

   To find occurrences of a pattern string within a text efficiently -> Option A

4. Quick Check:

   KMP = Pattern searching [OK]

Hint: KMP is all about fast pattern search in text [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP calculates factorials

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

easy

A. int[] lps = new int();

B. int lps = new int[pattern.Length];

C. int lps[] = new int[pattern.Length];

D. int[] lps = new int[pattern.Length];

Solution

1. Step 1: Understand array declaration in C#

   In C#, arrays are declared with type[], then new type[size]. So int[] lps = new int[pattern.Length]; is correct.

2. Step 2: Check other options

   int lps = new int[pattern.Length]; misses [] for array type, C uses invalid syntax, D uses C/C++ style which is invalid in C#.

3. Final Answer:

   int[] lps = new int[pattern.Length]; -> Option D

4. Quick Check:

   C# array syntax = int[] name = new int[size]; [OK]

Hint: Use int[] for arrays, not int alone [OK]

Common Mistakes:

• Missing [] in array type declaration
• Using C/C++ style array declaration in C#
• Trying to instantiate array without size

3. What will be the output of the following C# code snippet using KMP algorithm to find pattern "ABABC" in text "ABABABC"?

string text = "ABABABC";
string pattern = "ABABC";
List<int> matches = KMPSearch(pattern, text);
Console.WriteLine(string.Join(",", matches));

// Assume KMPSearch returns list of start indices where pattern matches text

medium

A. 0,2

B. 1

C. 2

D. No matches

Solution

1. Step 1: Analyze the text and pattern

   Text: A B A B A B C Pattern: A B A B C Check where pattern fully matches text starting index.

2. Step 2: Find matching index

   At index 0: text substring "ABABA" does not match "ABABC" (last char mismatch) At index 1: substring "BABAB" no match At index 2: substring "ABABC" matches pattern exactly.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Pattern found at index 2 only [OK]

Hint: Check substring matches carefully for exact pattern [OK]

Common Mistakes:

• Assuming multiple matches without checking full pattern
• Off-by-one errors in indexing
• Confusing partial matches as full matches

4. Identify the bug in this KMP prefix table (lps) computation code snippet in C#:

int[] ComputeLPS(string pattern) {
    int[] lps = new int[pattern.Length];
    int length = 0;
    int i = 1;
    while (i < pattern.Length) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

medium

A. Incorrect update of length in else block: should be length = lps[length - 1];

B. Wrong initialization of lps array size

C. Using while loop instead of for loop causes infinite loop

D. Missing return statement at the end

Solution

1. Step 1: Understand lps update logic

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

2. Step 2: Check other parts

   Array size is correct, while loop is valid, return statement exists. So only length update is wrong.

3. Final Answer:

   Incorrect update of length in else block: should be length = lps[length - 1]; -> Option A

4. Quick Check:

   lps update uses length-1 index [OK]

Hint: Use length-1 index when updating length on mismatch [OK]

Common Mistakes:

• Using lps[length] instead of lps[length - 1]
• Confusing loop types causing infinite loops
• Forgetting to return lps array

5. Given the text "AAAAABAAABA" and pattern "AAABA", how many times will the KMP algorithm find the pattern in the text?

hard

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Identify all occurrences of pattern in text

   Text: A A A A A B A A A B A Pattern: A A A B A Check each possible start index:

2. Step 2: Check matches at each index

   Index 0: substring "AAAAA" no (pattern ends with B) Index 1: substring "AAAAB" no (pattern ends with A) Index 2: substring "AAABA" yes (match 1) Index 3: substring "AABAA" no Index 4: substring "ABAAA" no Index 5: substring "BAAAB" no Index 6: substring "AAABA" yes (match 2) Index 7: substring "AABA" incomplete Index 8: substring "ABA" incomplete Check carefully for overlapping matches.

3. Step 3: Re-check for missed matches

   Check index 1 carefully: substring "AAAAB" pattern is "AAABA" so no match. Check index 0 carefully: substring "AAAAA" pattern ends with B, no match. Check index 6: "AAABA" matches pattern exactly (match 2). Check index 2: "AAABA" matches pattern exactly (match 1). No other matches found.

4. Step 4: Check index 3 for overlapping match

   At index 3: substring "AABAA" does not match pattern "AAABA". At index 4: substring "ABAAA" no match. At index 5: substring "BAAAB" no match. At index 7: substring "AABA" incomplete. So total matches found: 2.

5. Final Answer:

   2 -> Option B

6. Quick Check:

   Pattern found twice in text [OK]

Hint: Check each substring carefully for full pattern match [OK]

Common Mistakes:

• Counting partial matches as full matches
• Missing overlapping matches
• Off-by-one errors in substring indexing