← All topics
Quiz: String Matching — KMP and Rabin-Karp: questions with answers
10 questions, each with the answer and a short explanation.
Take the timed quiz + get a certificate →- Q1. What is the worst-case time of naive string matching for text length n and pattern length m?
- Q2. What does lps[i] store in KMP?
- Q3. What does this print? (code)
- Q4. When KMP finds a mismatch after j letters matched (j 0), what does it do?
- Q5. Why is KMP search O(n + m)?
- Q6. What does this print? (code)
- Q7. In Rabin-Karp, why compare the letters when two hashes are equal?
- Q8. What does this print? (code)
- Q9. When is Rabin-Karp especially useful compared with KMP?
- Q10. A string has length 9 and lps[8] = 6. What does that tell you?