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 pattern[] = { 'A', 'B', 'A', 'B', 'A', 'C' };
int prefix[] = {0, 0, 0, 0, 0, 0};
// KMP prefix table computation logic here
// Output prefix array after computation

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

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

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

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

💡 Hint

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

The prefix table for "ABABAC" is computed by comparing characters and updating the longest prefix-suffix lengths. The correct prefix table is [0, 0, 1, 2, 3, 0].

❓ Predict Output

intermediate

KMP search output for given text and pattern

What is the output (starting indices) of the KMP search for pattern "ABABC" in text "ABABABCABABC"?

DSA C

char text[] = "ABABABCABABC";
char pattern[] = "ABABC";
// KMP search logic
// Print all starting indices where pattern is found

A [0, 2, 7]

B [2, 7]

C [0, 5]

D [1, 6]

💡 Hint

Check carefully where the pattern fully matches in the text.

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

🔧 Debug

advanced

Identify the bug in prefix table computation

Given the following prefix table computation code snippet, what error will it cause when run with pattern "AAAAB"?

DSA C

int computePrefix(char* pattern, int length, int* prefix) {
    int j = 0;
    prefix[0] = 0;
    for (int i = 1; i < length; i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefix[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        prefix[i] = j;
    }
    return 0;
}

A Runtime error due to infinite loop

B Segmentation fault due to invalid prefix index access

C Correct prefix table computed without error

D Compilation error due to missing semicolon

💡 Hint

Check the line where j is updated inside the while loop.

For pattern "AAAAB", after prefix[0..3] = [0,1,2,3], at i=4 ('B' != pattern[3]='A'), the while loop sets j = prefix[3] = 3 repeatedly, causing an infinite loop.

🧠 Conceptual

advanced

Time complexity of KMP algorithm

What is the time complexity of the KMP pattern matching algorithm for a text of length n and pattern of length m?

A O(n + m)

B O(n * m)

C O(n^2)

D O(m^2)

💡 Hint

KMP avoids rechecking characters by using the prefix table.

KMP preprocesses the pattern in O(m) and searches the text in O(n), so total time is O(n + m).

🚀 Application

expert

Using KMP to find the longest prefix which is also suffix

Given a string s, how can the KMP prefix table be used to find the length of the longest prefix of s which is also a suffix (excluding the whole string)?

A Maximum value in the prefix table minus one gives the length

B The first value in the prefix table gives the length of the longest prefix-suffix

C The last value in the prefix table gives the length of the longest prefix-suffix

D Sum of all values in the prefix table gives the length

💡 Hint

The prefix table stores lengths of longest prefix-suffix for each prefix of the string.

The last value in the prefix table corresponds to the longest prefix which is also suffix for the entire string (excluding the whole string itself).

Practice

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

easy

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

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the total number of characters in the text

Solution

1. Step 1: Understand KMP's goal

   KMP algorithm is designed to find all occurrences of a pattern in a text efficiently.

2. Step 2: Identify how KMP works

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

3. Final Answer:

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

4. Quick Check:

   KMP = Efficient pattern search [OK]

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

Common Mistakes:

• Thinking KMP sorts or reverses strings
• Confusing KMP with simple substring search
• Assuming KMP counts characters only

2. Which of the following correctly declares the prefix (lps) array in C for KMP algorithm of size m?

easy

A. int *lps = malloc(m * sizeof(int));

B. int lps = new int[m];

C. int lps[m];

D. int lps[] = {m};

Solution

1. Step 1: Understand array declaration in C

   Static arrays like int lps[m]; require constant size or C99 support; dynamic allocation uses malloc.

2. Step 2: Identify correct dynamic allocation

   int *lps = malloc(m * sizeof(int)); correctly allocates memory for m integers dynamically.

3. Final Answer:

   int *lps = malloc(m * sizeof(int)); -> Option A

4. Quick Check:

   Dynamic array = malloc usage [OK]

Hint: Use malloc for dynamic arrays in C [OK]

Common Mistakes:

• Using Java-style array allocation in C
• Incorrect static array size syntax
• Misusing array initialization syntax

3. What will be the output of the following C code snippet using KMP prefix array computation for pattern "ABABC"?

int main() {
    char pattern[] = "ABABC";
    int m = 5, i = 1, len = 0;
    int lps[5] = {0};
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    for (int j = 0; j < m; j++) {
        printf("%d ", lps[j]);
    }
    return 0;
}

medium

A. 0 0 1 2 1

B. 0 1 0 1 2

C. 0 1 2 3 4

D. 0 0 1 2 0

Solution

1. Step 1: Compute lps array step-by-step for "ABABC"

   Index 0: 0; i=1: 'B' != 'A' (len=0) -> lps[1]=0, i=2; i=2: 'A' == 'A' -> len=1, lps[2]=1, i=3; i=3: 'B' == 'B' -> len=2, lps[3]=2, i=4; i=4: 'C' != 'A' (len=2) -> len=lps[1]=0, 'C' != 'A' -> lps[4]=0.

2. Step 2: Final lps array values

   The lps array is [0, 0, 1, 2, 0]. Output: 0 0 1 2 0

3. Final Answer:

   0 0 1 2 0 -> Option D

4. Quick Check:

   lps for "ABABC" = 0 0 1 2 0 [OK]

Hint: Trace lps step-by-step for each pattern char [OK]

Common Mistakes:

• Miscomputing fallback index in lps
• Confusing pattern characters during comparison
• Assuming lps always increases

4. Identify the bug in this KMP prefix array computation snippet and select the fix:

int i = 1, len = 0;
while (i <= m) {
    if (pattern[i] == pattern[len]) {
        len++;
        lps[i] = len;
        i++;
    } else {
        if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i] = 0;
            i++;
        }
    }
}

medium

A. Remove i++ inside else block

B. Initialize len to 1 instead of 0

C. Change loop condition to i < m

D. Use pattern[len+1] instead of pattern[len]

Solution

1. Step 1: Analyze loop boundary

   The loop runs while i <= m, but array indices go from 0 to m-1, so i == m causes out-of-bounds access.

2. Step 2: Correct loop condition

   Changing condition to i < m prevents accessing beyond array size.

3. Final Answer:

   Change loop condition to i < m -> Option C

4. Quick Check:

   Loop index must be less than array size [OK]

Hint: Loop till less than array size, not equal [OK]

Common Mistakes:

• Using <= instead of < causing overflow
• Incorrect initialization of len
• Misplacing increment statements

5. Given text "ABABDABACDABABCABAB" and pattern "ABABCABAB", how many times does the KMP algorithm find the pattern in the text?

hard

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Understand pattern occurrences

   Check the text for exact matches of pattern "ABABCABAB" (length 9).

2. Step 2: Locate matches in text

   Pattern matches fully at index 10 ("ABABCABAB" from positions 10-18) and also at index 0 ("ABABDABAC" partial mismatch at 4th char but KMP finds overlapping matches). Actually, KMP finds the pattern twice: once starting at index 0 (partial mismatch but KMP continues) and once at index 10 fully matching. The correct count is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Pattern found twice in text [OK]

Hint: Count full pattern matches in text using KMP [OK]

Common Mistakes:

• Counting partial matches as full
• Misidentifying additional matches (e.g., at index 14)
• Overlooking text length boundaries