Rabin Karp String Matching in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Rabin Karp string matching algorithm?

It uses hashing to find a pattern in a text by comparing hash values of the pattern and substrings of the text, reducing the number of direct character comparisons.

intermediate

Why does Rabin Karp use a rolling hash?

A rolling hash allows efficient computation of hash values for consecutive substrings by updating the previous hash instead of recalculating from scratch.

intermediate

What happens if two substrings have the same hash value in Rabin Karp?

Since hash collisions can occur, the algorithm checks the actual characters of the substrings to confirm if they really match.

advanced

What is the average and worst-case time complexity of Rabin Karp?

Average case is O(n + m) where n is text length and m is pattern length. Worst case is O(n*m) due to hash collisions requiring full substring checks.

intermediate

Explain the role of the modulus in Rabin Karp hashing.

The modulus keeps hash values within a fixed range to avoid overflow and helps in distributing hash values uniformly to reduce collisions.

What does Rabin Karp primarily use to speed up pattern matching?

A Hashing of substrings

B Sorting the text

C Binary search

D Dynamic programming

Rabin Karp uses hashing to quickly compare the pattern with substrings of the text.

What is a rolling hash in Rabin Karp?

A A hash that sorts characters

B A hash that is recalculated fully each time

C A hash that ignores collisions

D A hash that updates efficiently for the next substring

Rolling hash updates the hash value by removing the old character and adding the new one efficiently.

If two substrings have the same hash, what does Rabin Karp do next?

A Assumes they match without checking

B Ignores the substrings

C Checks characters one by one to confirm match

D Restarts the algorithm

Because of possible collisions, Rabin Karp verifies the actual substring characters.

What is the worst-case time complexity of Rabin Karp?

A O(log n)

B O(n*m)

C O(m^2)

D O(n + m)

Worst case happens when many hash collisions cause repeated substring checks, leading to O(n*m).

Why is modulus used in Rabin Karp hashing?

A To keep hash values in a fixed range and reduce collisions

B To sort the hash values

C To increase hash values indefinitely

D To ignore characters in the pattern

Modulus keeps hash values manageable and helps distribute them evenly.

Describe how the Rabin Karp algorithm finds a pattern in a text using hashing.

Think about how hash values help avoid checking every character every time.

Explain why Rabin Karp might sometimes perform slower than expected and how it handles that situation.

Consider what happens when different substrings have the same hash.