Algorithm

Why do we use Rabin-Karp Algorithm?

When we want to find a pattern in a large text, a naive approach compares each possible substring character by character. That’s slow for large texts and multiple patterns and will result in TLE.

Instead of comparing strings directly, Rabin-Karp Algorithm converts them into numbers using a hash function. Ideally, two strings with the same hash are same. Using a smart hash function, we can update the hash value in constant time when we use sliding window technique to check for matching substrings.

We still compare the actual characters even after a hash match because different strings can sometimes produce the same hash value. To ensure accuracy, whenever the hash of a substring in the text matches the pattern's hash, we perform a direct character-by-character comparison to confirm that the match is genuine.

First, calculate a numeric hash for the pattern you are trying to find.
Then, take the first part of the text (of the same length as the pattern) and calculate its hash.
Compare this hash with the pattern's hash.

If they are not the same, move to the next substring.
If they are the same, then compare the actual characters of the substring and the pattern to confirm a real match. Sometimes, even if hash values of two strings might match, there's a possibility that the string might not be equal.

Slide the window one character forward in the text and update the hash efficiently without redoing the whole calculation from scratch.
Repeat the comparison process — check the new hash against the pattern’s hash, and if needed, do the character-by-character confirmation.
Continue this sliding and checking process until you've examined all possible substrings in the text.
Finally, collect all positions where a confirmed match was found.