Rabin–Karp String Matching Algorithm Code Implementations
Complete Rabin–Karp String Matching Algorithm code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Rabin–Karp String Matching Algorithm Guide · Launch Interactive Visualizer
C++ Implementation
// Rabin-Karp Algorithm Implementation in C++
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <chrono>
class RabinKarpAlgorithm {
public:
// Rabin-Karp Search Algorithm
static std::vector<int> rabinKarpSearch(const std::string& text, const std::string& pattern, int prime = 101) {
int n = text.length();
int m = pattern.length();
std::vector<int> matches;
if (m > n) return matches;
// Calculate hash for pattern and first window of text
int patternHash = 0;
int textHash = 0;
int h = 1;
// Calculate h = pow(prime, m-1) % prime
for (int i = 0; i < m - 1; i++) {
h = (h * 256) % prime;
}
// Calculate hash for pattern and first window
for (int i = 0; i < m; i++) {
patternHash = (256 * patternHash + pattern[i]) % prime;
textHash = (256 * textHash + text[i]) % prime;
}
// Slide the pattern over text one by one
for (int i = 0; i <= n - m; i++) {
// Check if hash values match
if (patternHash == textHash) {
// Check if characters actually match
if (text.substr(i, m) == pattern) {
matches.push_back(i);
}
}
// Calculate hash for next window
if (i < n - m) {
textHash = (256 * (textHash - text[i] * h) + text[i + m]) % prime;
if (textHash < 0) {
textHash += prime;
}
}
}
return matches;
}
// Rabin-Karp with multiple hash functions
static std::vector<std::pair<int, std::vector<int>>> rabinKarpMultipleHashes(
const std::string& text, const std::string& pattern, const std::vector<int>& primes) {
std::vector<std::pair<int, std::vector<int>>> results;
for (int prime : primes) {
std::vector<int> matches = rabinKarpSearch(text, pattern, prime);
results.emplace_back(prime, matches);
}
return results;
}
// Rabin-Karp for multiple patterns
static std::unordered_map<std::string, std::vector<int>> rabinKarpMultiplePatterns(
const std::string& text, const std::vector<std::string>& patterns, int prime = 101) {
std::unordered_map<std::string, std::vector<int>> results;
for (const auto& pattern : patterns) {
results[pattern] = rabinKarpSearch(text, pattern, prime);
}
return results;
}
// Rabin-Karp with performance measurement
struct RabinKarpResult {
std::vector<int> matches;
int count;
long long executionTime;
RabinKarpResult(const std::vector<int>& m, int c, long long t)
: matches(m), count(c), executionTime(t) {}
};
static RabinKarpResult rabinKarpWithTiming(const std::string& text, const std::string& pattern, int prime = 101) {
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> matches = rabinKarpSearch(text, pattern, prime);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
return RabinKarpResult(matches, matches.size(), duration.count());
}
// Performance comparison
static void comparePerformance(const std::string& text, const std::string& pattern) {
auto start = std::chrono::high_resolution_clock::now();
std::vector<int> matches = rabinKarpSearch(text, pattern);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Rabin-Karp Search: " << matches.size() << " matches found in "
<< duration.count() << " μs" << std::endl;
}
};JAVA Implementation
// Rabin-Karp Algorithm Implementation in Java
import java.util.*;
public class RabinKarpAlgorithm {
// Rabin-Karp Search Algorithm
public static List<Integer> rabinKarpSearch(String text, String pattern, int prime) {
int n = text.length();
int m = pattern.length();
List<Integer> matches = new ArrayList<>();
if (m > n) return matches;
// Calculate hash for pattern and first window of text
int patternHash = 0;
int textHash = 0;
int h = 1;
// Calculate h = pow(prime, m-1) % prime
for (int i = 0; i < m - 1; i++) {
h = (h * 256) % prime;
}
// Calculate hash for pattern and first window
for (int i = 0; i < m; i++) {
patternHash = (256 * patternHash + pattern.charAt(i)) % prime;
textHash = (256 * textHash + text.charAt(i)) % prime;
}
// Slide the pattern over text one by one
for (int i = 0; i <= n - m; i++) {
// Check if hash values match
if (patternHash == textHash) {
// Check if characters actually match
if (text.substring(i, i + m).equals(pattern)) {
matches.add(i);
}
}
// Calculate hash for next window
if (i < n - m) {
textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % prime;
if (textHash < 0) {
textHash += prime;
}
}
}
return matches;
}
// Rabin-Karp with multiple hash functions
public static List<Map<String, Object>> rabinKarpMultipleHashes(String text, String pattern, int[] primes) {
List<Map<String, Object>> results = new ArrayList<>();
for (int prime : primes) {
List<Integer> matches = rabinKarpSearch(text, pattern, prime);
Map<String, Object> result = new HashMap<>();
result.put("prime", prime);
result.put("matches", matches);
results.add(result);
}
return results;
}
// Rabin-Karp for multiple patterns
public static Map<String, List<Integer>> rabinKarpMultiplePatterns(String text, String[] patterns, int prime) {
Map<String, List<Integer>> results = new HashMap<>();
for (String pattern : patterns) {
results.put(pattern, rabinKarpSearch(text, pattern, prime));
}
return results;
}
// Rabin-Karp with case-insensitive search
public static List<Integer> rabinKarpCaseInsensitive(String text, String pattern, int prime) {
return rabinKarpSearch(text.toLowerCase(), pattern.toLowerCase(), prime);
}
// Rabin-Karp with performance measurement
public static class RabinKarpResult {
public List<Integer> matches;
public int count;
public long executionTime;
public RabinKarpResult(List<Integer> matches, int count, long executionTime) {
this.matches = matches;
this.count = count;
this.executionTime = executionTime;
}
}
public static RabinKarpResult rabinKarpWithTiming(String text, String pattern, int prime) {
long startTime = System.nanoTime();
List<Integer> matches = rabinKarpSearch(text, pattern, prime);
long endTime = System.nanoTime();
return new RabinKarpResult(matches, matches.size(), endTime - startTime);
}
}JAVASCRIPT Implementation
// Rabin-Karp Algorithm Implementation in JavaScript
// Rabin-Karp Search Algorithm
function rabinKarpSearch(text, pattern, prime = 101) {
const n = text.length;
const m = pattern.length;
const matches = [];
if (m > n) return matches;
// Calculate hash for pattern and first window of text
let patternHash = 0;
let textHash = 0;
let h = 1;
// Calculate h = pow(prime, m-1) % prime
for (let i = 0; i < m - 1; i++) {
h = (h * 256) % prime;
}
// Calculate hash for pattern and first window
for (let i = 0; i < m; i++) {
patternHash = (256 * patternHash + pattern.charCodeAt(i)) % prime;
textHash = (256 * textHash + text.charCodeAt(i)) % prime;
}
// Slide the pattern over text one by one
for (let i = 0; i <= n - m; i++) {
// Check if hash values match
if (patternHash === textHash) {
// Check if characters actually match
let match = true;
for (let j = 0; j < m; j++) {
if (text[i + j] !== pattern[j]) {
match = false;
break;
}
}
if (match) {
matches.push(i);
}
}
// Calculate hash for next window
if (i < n - m) {
textHash = (256 * (textHash - text.charCodeAt(i) * h) + text.charCodeAt(i + m)) % prime;
if (textHash < 0) {
textHash += prime;
}
}
}
return matches;
}
// Rabin-Karp with multiple hash functions
function rabinKarpMultipleHashes(text, pattern, primes = [101, 103, 107]) {
const results = [];
for (const prime of primes) {
const matches = rabinKarpSearch(text, pattern, prime);
results.push({ prime, matches });
}
return results;
}
// Rabin-Karp with rolling hash optimization
function rabinKarpRollingHash(text, pattern) {
const n = text.length;
const m = pattern.length;
const matches = [];
if (m > n) return matches;
const base = 256;
const prime = 101;
// Precompute powers of base
const powers = new Array(m);
powers[0] = 1;
for (let i = 1; i < m; i++) {
powers[i] = (powers[i - 1] * base) % prime;
}
// Calculate hash for pattern
let patternHash = 0;
for (let i = 0; i < m; i++) {
patternHash = (patternHash + pattern.charCodeAt(i) * powers[m - 1 - i]) % prime;
}
// Calculate hash for first window
let textHash = 0;
for (let i = 0; i < m; i++) {
textHash = (textHash + text.charCodeAt(i) * powers[m - 1 - i]) % prime;
}
// Slide and check
for (let i = 0; i <= n - m; i++) {
if (patternHash === textHash) {
// Verify match
let match = true;
for (let j = 0; j < m; j++) {
if (text[i + j] !== pattern[j]) {
match = false;
break;
}
}
if (match) {
matches.push(i);
}
}
// Update hash for next window
if (i < n - m) {
textHash = ((textHash - text.charCodeAt(i) * powers[m - 1]) * base + text.charCodeAt(i + m)) % prime;
if (textHash < 0) textHash += prime;
}
}
return matches;
}
// Rabin-Karp for multiple patterns
function rabinKarpMultiplePatterns(text, patterns, prime = 101) {
const results = {};
for (const pattern of patterns) {
results[pattern] = rabinKarpSearch(text, pattern, prime);
}
return results;
}
// Rabin-Karp with case-insensitive search
function rabinKarpCaseInsensitive(text, pattern, prime = 101) {
const lowerText = text.toLowerCase();
const lowerPattern = pattern.toLowerCase();
return rabinKarpSearch(lowerText, lowerPattern, prime);
}
// Rabin-Karp with performance measurement
function rabinKarpWithTiming(text, pattern, prime = 101) {
const startTime = performance.now();
const matches = rabinKarpSearch(text, pattern, prime);
const endTime = performance.now();
return {
matches,
count: matches.length,
executionTime: endTime - startTime
};
}
// Rabin-Karp for finding repeated substrings
function rabinKarpFindRepeatedSubstrings(text, minLength = 2) {
const n = text.length;
const repeated = new Set();
for (let len = minLength; len <= n / 2; len++) {
const hashMap = new Map();
for (let i = 0; i <= n - len; i++) {
const substring = text.substring(i, i + len);
const hash = rabinKarpSearch(text, substring, 101);
if (hash.length > 1) {
repeated.add(substring);
}
}
}
return Array.from(repeated);
}PYTHON Implementation
# Rabin-Karp Algorithm Implementation in Python
def rabin_karp_search(text, pattern, prime=101):
"""Rabin-Karp Search Algorithm"""
n, m = len(text), len(pattern)
matches = []
if m > n:
return matches
# Calculate hash for pattern and first window of text
pattern_hash = 0
text_hash = 0
h = 1
# Calculate h = pow(prime, m-1) % prime
for i in range(m - 1):
h = (h * 256) % prime
# Calculate hash for pattern and first window
for i in range(m):
pattern_hash = (256 * pattern_hash + ord(pattern[i])) % prime
text_hash = (256 * text_hash + ord(text[i])) % prime
# Slide the pattern over text one by one
for i in range(n - m + 1):
# Check if hash values match
if pattern_hash == text_hash:
# Check if characters actually match
if text[i:i + m] == pattern:
matches.append(i)
# Calculate hash for next window
if i < n - m:
text_hash = (256 * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
if text_hash < 0:
text_hash += prime
return matches
def rabin_karp_multiple_hashes(text, pattern, primes=[101, 103, 107]):
"""Rabin-Karp with multiple hash functions"""
results = []
for prime in primes:
matches = rabin_karp_search(text, pattern, prime)
results.append({'prime': prime, 'matches': matches})
return results
def rabin_karp_rolling_hash(text, pattern):
"""Rabin-Karp with rolling hash optimization"""
n, m = len(text), len(pattern)
matches = []
if m > n:
return matches
base = 256
prime = 101
# Precompute powers of base
powers = [1] * m
for i in range(1, m):
powers[i] = (powers[i - 1] * base) % prime
# Calculate hash for pattern
pattern_hash = 0
for i in range(m):
pattern_hash = (pattern_hash + ord(pattern[i]) * powers[m - 1 - i]) % prime
# Calculate hash for first window
text_hash = 0
for i in range(m):
text_hash = (text_hash + ord(text[i]) * powers[m - 1 - i]) % prime
# Slide and check
for i in range(n - m + 1):
if pattern_hash == text_hash:
# Verify match
if text[i:i + m] == pattern:
matches.append(i)
# Update hash for next window
if i < n - m:
text_hash = ((text_hash - ord(text[i]) * powers[m - 1]) * base + ord(text[i + m])) % prime
if text_hash < 0:
text_hash += prime
return matches
def rabin_karp_multiple_patterns(text, patterns, prime=101):
"""Rabin-Karp for multiple patterns"""
results = {}
for pattern in patterns:
results[pattern] = rabin_karp_search(text, pattern, prime)
return results
def rabin_karp_case_insensitive(text, pattern, prime=101):
"""Rabin-Karp with case-insensitive search"""
return rabin_karp_search(text.lower(), pattern.lower(), prime)
def rabin_karp_with_timing(text, pattern, prime=101):
"""Rabin-Karp with performance measurement"""
import time
start_time = time.time()
matches = rabin_karp_search(text, pattern, prime)
end_time = time.time()
return {
'matches': matches,
'count': len(matches),
'execution_time': end_time - start_time
}
def rabin_karp_find_repeated_substrings(text, min_length=2):
"""Rabin-Karp for finding repeated substrings"""
n = len(text)
repeated = set()
for length in range(min_length, n // 2 + 1):
for i in range(n - length + 1):
substring = text[i:i + length]
matches = rabin_karp_search(text, substring, 101)
if len(matches) > 1:
repeated.add(substring)
return list(repeated)