KMP Pattern Matching Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does KMP stand for in the KMP Pattern Matching Algorithm?

KMP stands for Knuth-Morris-Pratt, the last names of the three people who created this efficient pattern searching algorithm.

beginner

What is the main advantage of the KMP algorithm over the naive pattern matching approach?

KMP avoids rechecking characters that have already been matched by using a precomputed table, making it faster especially for large texts and patterns.

intermediate

What is the purpose of the 'lps' (Longest Prefix Suffix) array in KMP?

The 'lps' array stores the length of the longest proper prefix of the pattern that is also a suffix for each prefix of the pattern. It helps decide where to continue matching after a mismatch.

intermediate

In KMP, what happens when a mismatch occurs after some matches?

Instead of starting over, KMP uses the 'lps' array to skip characters and continue matching from the longest prefix that matches a suffix, saving time.

intermediate

What is the time complexity of the KMP Pattern Matching Algorithm?

The time complexity is O(n + m), where n is the length of the text and m is the length of the pattern, because each character is processed at most twice.

What does the 'lps' array in KMP represent?

A Longest prefix which is also suffix for pattern prefixes

B Length of the pattern

C Positions of pattern matches in text

D Number of mismatches found

The 'lps' array stores the length of the longest proper prefix which is also a suffix for each prefix of the pattern.

What is the main benefit of using KMP over naive pattern matching?

A It uses less memory

B It finds all substrings in constant time

C It works only on small texts

D It avoids rechecking characters after mismatch

KMP avoids rechecking characters by using the 'lps' array, making it more efficient than naive matching.

If a mismatch occurs at pattern index 3, where does KMP jump next?

A Back to pattern start

B To the index given by lps[2]

C To the next character in text

D To the end of the pattern

KMP uses the lps value of the previous index (3-1=2) to decide where to continue matching.

What is the worst-case time complexity of KMP?

A O(n*m)

B O(n^2)

C O(n + m)

D O(m^2)

KMP runs in linear time relative to text and pattern lengths, O(n + m).

Which step is NOT part of the KMP algorithm?

A Restart matching from the beginning after mismatch

B Precompute the lps array

C Compare characters of text and pattern

D Use lps to skip unnecessary comparisons

KMP does NOT restart from the beginning after mismatch; it uses lps to skip ahead.

Explain how the 'lps' array is constructed and how it helps in pattern matching.

Think about prefixes and suffixes in the pattern.

Describe the steps KMP takes when a mismatch happens during pattern matching.

Focus on how KMP avoids rechecking characters.