AntInLoop

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)