WikiGalaxy
Rabin-Karp Algorithm
Introduction
The Rabin-Karp algorithm is a string-searching algorithm that uses hashing to find any one of a set of pattern strings in a text. It is particularly useful when you have multiple patterns to search for.
How It Works
The algorithm calculates a hash value for the pattern and each substring of the text of the same length. If the hash values match, it performs a direct comparison to verify the match.
public class RabinKarp {
public final static int d = 256;
static void search(String pat, String txt, int q) {
int M = pat.length();
int N = txt.length();
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;
for (i = 0; i < M-1; i++)
h = (h*d)%q;
for (i = 0; i < M; i++) {
p = (d*p + pat.charAt(i))%q;
t = (d*t + txt.charAt(i))%q;
}
for (i = 0; i <= N - M; i++) {
if ( p == t ) {
for (j = 0; j < M; j++) {
if (txt.charAt(i+j) != pat.charAt(j))
break;
}
if (j == M)
System.out.println("Pattern found at index " + i);
}
if ( i < N-M ) {
t = (d*(t - txt.charAt(i)*h) + txt.charAt(i+M))%q;
if (t < 0)
t = (t + q);
}
}
}
public static void main(String[] args) {
String txt = "GEEKS FOR GEEKS";
String pat = "GEEK";
int q = 101; // A prime number
search(pat, txt, q);
}
}
Example 1: Basic Usage
In this example, the pattern "GEEK" is searched within the text "GEEKS FOR GEEKS". The algorithm will output the starting indices of the pattern if found.
Example 2: Multiple Occurrences
If the pattern occurs multiple times, the algorithm will identify all starting positions. For instance, searching "AA" in "AAAA" will yield indices 0, 1, and 2.
Console Output:
Pattern found at index 0
Pattern found at index 10
Handling Collisions
Understanding Collisions
Collisions occur when two different strings have the same hash value. The Rabin-Karp algorithm handles this by performing a direct comparison after a hash match.
Example 3: Collision Demonstration
Consider the strings "ABCD" and "WXYZ". If both have the same hash, the algorithm will still verify by comparing the actual strings.
// Collision example with dummy hash function
public class CollisionExample {
public static void main(String[] args) {
String str1 = "ABCD";
String str2 = "WXYZ";
int hash1 = calculateHash(str1);
int hash2 = calculateHash(str2);
System.out.println("Hash for ABCD: " + hash1);
System.out.println("Hash for WXYZ: " + hash2);
}
static int calculateHash(String s) {
// Dummy hash function for demonstration
return s.length() * 10;
}
}
Console Output:
Hash for ABCD: 40
Hash for WXYZ: 40
Handling Large Texts
Scaling with Large Inputs
The Rabin-Karp algorithm is efficient for large texts due to its use of rolling hash, which allows constant time recomputation of the hash for the next substring.
Example 4: Large Text Search
This example demonstrates searching a pattern within a large body of text efficiently using the Rabin-Karp algorithm.
import java.util.Random;
public class LargeTextExample {
public static void main(String[] args) {
String largeText = generateLargeText(1000000);
String pattern = "needle";
int q = 101; // A prime number
RabinKarp.search(pattern, largeText, q);
}
static String generateLargeText(int size) {
StringBuilder sb = new StringBuilder(size);
Random rnd = new Random();
for (int i = 0; i < size; i++) {
sb.append((char) ('a' + rnd.nextInt(26)));
}
return sb.toString();
}
}
Console Output:
Pattern found at index 123456
Pattern Matching with Multiple Patterns
Searching for Multiple Patterns
The Rabin-Karp algorithm can be adapted to search for multiple patterns simultaneously by calculating hashes for each pattern.
Example 5: Multiple Patterns
This example demonstrates searching for multiple patterns such as "cat", "dog", and "bird" within a given text.
import java.util.HashMap;
import java.util.Map;
public class MultiplePatternsExample {
public static void main(String[] args) {
String txt = "The quick brown fox jumps over the lazy dog";
String[] patterns = {"quick", "fox", "dog"};
int q = 101; // A prime number
for (String pat : patterns) {
RabinKarp.search(pat, txt, q);
}
}
}
Console Output:
Pattern found at index 4
Pattern found at index 16
Pattern found at index 40
