Search Pattern (Rabin-Karp Algorithm) in Java

The Rabin-Karp Algorithm is an efficient string-matching method that uses hashing to find a pattern within a text. Rather than examining each character individually, it computes a hash value for the pattern and compares it with the hash values of text substrings. When a hash match occurs, the algorithm performs a character-wise check to validate the match.

Example 1: Finding a Word in a Sentence

Input:

Text = "WELCOME TO JAVA PROGRAMMING"

Pattern = "JAVA"

Output:

Pattern found at index: 11

Example 2: Searching for Multiple Occurrences

Input:

Text = "ABABCABAB"

Pattern = "ABAB"

Output:

Pattern found at index: 0, 5

How to Compute Hash Value in Rabin-Karp?

Step 1: Select Base and Modulus

Choose a prime number q as the modulus to minimize hash collisions and prevent overflow. Set d as the base, which represents the number of possible characters (e.g., 256 for ASCII).

Step 2: Initialize Hash Values

Set the initial hash values of both the pattern and the first window of text to zero.

Step 3: Compute Initial Hash for Pattern and Text

Traverse the pattern and the first segment of text, computing their hash values using:

Step 4: Slide the Pattern Across the Text

Calculate the hash value for the first substring in the text, then shift the pattern over the text one position at a time.

Step 5: Update the Hash for Each Shift

For each shift, update the hash using:

This efficiently removes the contribution of the outgoing character and adds the new character.

Step 6: Check for Matches

If a substring's hash matches the pattern’s hash, perform a character-by-character comparison to confirm the match, as different substrings may produce the same hash.

Top of Form

Bottom of Form

Algorithm

Step 1: Compute the hash value of the specified pattern and the initial window of the text employing a rolling hash function while precomputing the hash base for more efficient sliding.

Step 2: Move through the text by advancing the window one character at a time and compare the current window's hash value with that of the pattern.

Step 3: When the hash values are the same, carry out a character-by-character comparison between the pattern and the current text window to verify a legitimate match.

Step 4: Calculate the hash for the upcoming window by eliminating the initial character, incorporating the subsequent character, and making adjustments for negative values if necessary.

Step 5: Keep moving the window, look for matches, revise the hash values, and display all positions where the pattern appears in the text.

Let’s implement the above steps in a Java program.

File Name: RabinKarp.java

Output:

 
Match found at index: 24   

Time Complexity: The worst-case complexity is O(N × M) due to hash collisions, while the average case runs in O(N + M) using efficient rolling hash computations.

Auxiliary Space Complexity: The algorithm requires only a few integer variables for hash calculations, making its auxiliary space complexity O(1).