Rabin-Karp Algorithm for Pattern Matching

1. The Rabin-Karp Strategy: Hashing Meets Sliding Window

The core idea of the Rabin-Karp algorithm is to avoid the expensive character-by-character comparison of a naive search. Instead of comparing strings, we'll compare their hash values.

The overall strategy is as follows:

1. Hash the Pattern: Calculate the hash of the pattern P you're searching for.
2. Initial Window Hash: Calculate the hash of the first substring (or "window") of the text T that has the same length as the pattern.
3. Slide and Compare: Slide the window across the text one character at a time. In each step:
   • Compare the hash of the current text window with the hash of the pattern.
   • If the hashes do not match, the strings cannot be equal, so we move on.
   • If the hashes do match, it's a potential match. This could be a genuine match or a "spurious hit" (a hash collision). We must then perform a direct character-by-character comparison to verify. If it's a real match, we record the starting index.
   • "Roll" the hash to the next window in O(1) time.

This process is visualized well in the following image.

To get a clearer conceptual understanding, let's watch a short segment that introduces this idea.

2. Spurious Hits and the Importance of a Good Hash Function

As the video you just watched demonstrates, a simple hash function (like summing character values) is easy to compute but can lead to many spurious hits—cases where the hashes match but the strings do not. This degrades performance because each spurious hit forces an expensive O(M) character-by-character check, where M is the pattern length.

Let's see an example of this worst-case scenario.

This is precisely why we use the polynomial rolling hash that you learned in the previous lesson. By weighting characters based on their position, we dramatically reduce the probability of collisions.

The formula we will use is:
$\text{hash}(s)=(s[0]\cdot {\text{base}}^{M-1}+s[1]\cdot {\text{base}}^{M-2}+\cdots +s[M-1]\cdot {\text{base}}^0)(\mathrm{mod}\text{mod})$

3. The Rolling Mechanism in Action

The real power of Rabin-Karp comes from updating the hash in O(1) time. As a refresher, to move the window from T[i...i+M-1] to T[i+1...i+M], we:

1. Subtract the value of the character leaving the window (T[i]).
2. Shift the remaining hash value (multiply by the base).
3. Add the value of the new character entering the window (T[i+M]).

The formula for the new hash (hash_new) based on the old hash (hash_old) is:
${\text{hash}}_{\text{new}}=\left(({\text{hash}}_{\text{old}}-T[i]\cdot {\text{base}}^{M-1})\cdot \text{base}+T[i+M]\right)(\mathrm{mod}\text{mod})$

This process is explained very clearly in the following segment.

A crucial point mentioned at the end of that clip is managing the size of the hash values. By performing all calculations modulo a large prime number (mod), we prevent integer overflow and keep the hashes manageable.

4. Java Implementation of Rabin-Karp

Now, let's bring everything together in a Java implementation. Your goal is to find all occurrences of a pattern in a text and return a list of their starting indices.

This implementation will follow the logic we've discussed:

• Set up constants for base and mod.
• Pre-compute base^(M-1) to facilitate the O(1) update.
• Calculate initial hashes for the pattern and the first window of the text.
• Loop through the text, comparing hashes and verifying matches.
• Use the rolling hash formula to update the text window's hash in each iteration.

Let's break down that tricky rolling hash update line from the code:
windowHash = (base * (windowHash - text.charAt(i) * h) + text.charAt(i + m)) % mod;

• text.charAt(i) * h: This is the contribution of the leftmost character, T[i]. h is pre-calculated as base^(M-1) % mod.
• windowHash - ...: We subtract this contribution from the old hash.
• base * (...): We shift the remaining hash to the left.
• + text.charAt(i + m): We add the new character's value.
• % mod: We take the modulus to keep the result in range. The check for windowHash < 0 is crucial because in Java, the % operator can return a negative result, which we must correct by adding mod to bring it back into the [0, mod-1] range.

5. Complexity Analysis

Let N be the length of the text and M be the length of the pattern.

• Time Complexity:

  • Average Case: O(N + M). This is the typical performance. We spend O(M) to compute the initial hashes and then O(N-M) to slide the window, with each step being O(1) for the hash update and comparison. Collisions are rare, so the verification cost is minimal.
  • Worst Case: O(N * M). As discussed, this occurs with frequent hash collisions.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space for variables to store the hashes, indices, and constants, regardless of the input size.

Conclusion

You have now successfully implemented the Rabin-Karp algorithm, a clever and practical application of the rolling hash technique. By trading guaranteed worst-case performance for excellent average-case speed, it provides an efficient way to solve pattern matching problems.

Key Takeaways:

• Rabin-Karp combines the sliding window technique with polynomial rolling hash.
• It achieves an O(1) average time for comparing the pattern against each text substring by comparing hashes.
• A hash match is only a potential match; it must be verified with a character-by-character comparison to handle collisions.
• The algorithm's efficiency hinges on a good hash function that minimizes collisions.
• The time complexity is O(N+M) on average but can degrade to O(N*M) in the worst case. The space complexity is O(1).

Preview of the next lesson:
While Rabin-Karp is very fast on average, its O(N*M) worst-case can be a concern. In our next lesson, we will begin our journey into another famous pattern matching algorithm: Knuth-Morris-Pratt (KMP). KMP is remarkable because it guarantees O(N+M) time complexity in all cases by using a clever pre-computation on the pattern to avoid redundant comparisons. We'll start by learning to build its core component: the Longest Proper Prefix which is also a Suffix (LPS) array.