KMP Pattern Matching Algorithm in DSA Python - 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 computer scientists who created this efficient pattern matching 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 'Longest Prefix Suffix' (LPS) 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 characters have matched?

Instead of restarting from the next character in the text, KMP uses the LPS array to shift the pattern to the right position, skipping unnecessary comparisons.

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 Length of the pattern

B Positions of pattern matches in text

C Number of mismatches found

D Length of longest prefix which is also suffix for pattern prefixes

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

Why is KMP faster than naive pattern matching?

A It uses a precomputed table to avoid rechecking characters

B It checks all characters twice

C It uses random guessing

D It only works on small texts

KMP uses the LPS array to skip unnecessary comparisons, avoiding rechecking characters.

What is the worst-case time complexity of KMP?

A O(n + m)

B O(n * m)

C O(n^2)

D O(m^2)

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

When a mismatch occurs in KMP, what does the algorithm do?

A Stops the search

B Restarts matching from the next character in text

C Uses LPS array to shift pattern without rechecking matched characters

D Skips the entire pattern

KMP uses the LPS array to shift the pattern smartly, avoiding rechecking matched characters.

What is the first step in the KMP algorithm?

A Reverse the pattern

B Compute the LPS array for the pattern

C Search the pattern in the text directly

D Sort the text

KMP first computes the LPS array to know how to shift the pattern during matching.

Explain how the LPS array is constructed in the KMP algorithm and why it is important.

Think about matching prefixes and suffixes within the pattern itself.

Describe the process of pattern matching in KMP when a mismatch occurs after some characters matched.

Focus on how KMP shifts the pattern smartly instead of naive restarting.