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).