Skills101
← All practice quizzes

Quiz: String Matching — KMP and Rabin-Karp

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Find every place a pattern appears in a text. Start with the simple O(n · m) search, then learn how KMP's prefix table and Rabin-Karp's rolling hash avoid repeated work.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    What is the worst-case time of naive string matching for text length n and pattern length m?

  2. Question 2

    What does lps[i] store in KMP?

  3. Question 3

    What does this print?

    def build_lps(p):
        lps, k = [0] * len(p), 0
        for i in range(1, len(p)):
            while k > 0 and p[i] != p[k]:
                k = lps[k - 1]
            if p[i] == p[k]:
                k += 1
            lps[i] = k
        return lps
    print(build_lps("AABAAA"))
    
  4. Question 4

    When KMP finds a mismatch after j letters matched (j > 0), what does it do?

  5. Question 5

    Why is KMP search O(n + m)?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →