Rabin Karp String Matching in DSA C - 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

How does Rabin Karp handle hash collisions?

When hash values match, Rabin Karp checks the actual characters of the substring and pattern to confirm a real match, avoiding false positives from collisions.

intermediate

What is the rolling hash technique in Rabin Karp?

Rolling hash efficiently computes the hash of the next substring by removing the leading character and adding the trailing character, avoiding full recomputation.

intermediate

Why is a prime number often used as the modulus in Rabin Karp hashing?

Using a prime modulus reduces the chance of hash collisions and helps distribute hash values more uniformly.

intermediate

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 causing many character comparisons.

What does Rabin Karp use to quickly compare the pattern with substrings of the text?

A Direct character by character comparison

B Hash values

C Sorting the text

D Binary search

Rabin Karp uses hash values to quickly compare the pattern with substrings, reducing direct comparisons.

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

A They are always the same substring

B The algorithm ignores the substring

C The algorithm checks characters to confirm a match

D The algorithm restarts

Hash collisions can occur, so Rabin Karp verifies by checking characters when hash values match.

What is the purpose of the rolling hash in Rabin Karp?

A To efficiently update the hash when moving to the next substring

B To compute hash from scratch each time

C To sort the pattern

D To reverse the text

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

Why is a prime number used as modulus in Rabin Karp hashing?

A To reduce hash collisions

B To make the hash smaller

C To increase collisions

D To sort the text

Prime modulus helps distribute hash values evenly and reduces collisions.

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

A O(n + m)

B O(n log m)

C O(m^2)

D O(n * m)

Worst case is O(n*m) due to many hash collisions causing repeated character checks.

Explain how Rabin Karp uses hashing and rolling hash to find a pattern in a text.

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

Describe the advantages and disadvantages of Rabin Karp compared to simple brute force string matching.

Consider speed and when it might slow down.