Searching Algorithm
Rabin-Karp

Rabin-Karp

The Rabin-Karp Algorithm is a string-searching algorithm that efficiently searches for a pattern within a given text using hashing techniques. It works by comparing hash values of the pattern with the hash values of the substrings in the text, reducing the need for individual character comparisons in certain cases.

How Rabin-Karp Algorithm Works

  1. Hashing: Compute the hash value of the pattern and hash values of substrings in the text.

  2. Matching: Compare the hash values of the pattern with the hash values of the text substrings.

  3. Character Comparison: If the hash values match, perform a character-by-character comparison to avoid false positives.

Key Features

  • Hashing: It utilizes hashing techniques to compare strings efficiently, reducing the need for extensive character comparisons.

  • Sliding Window: The algorithm utilizes a sliding window approach, computing the hash values as it slides along the text.

Efficiency

  • Time Complexity: The average time complexity of the Rabin-Karp Algorithm is O(n+m), where n is the length of the text and m is the length of the pattern. However, worst-case complexity might reach O(n*m).

  • Space Complexity: The space complexity is O(1), making it more memory-efficient.

Applications

  • String Matching: Used in various applications requiring string pattern matching within larger texts.

Advantages

  • Hashing Technique: Utilizes hash values for pattern matching, which speeds up the search process.

  • Sliding Window: Employs a sliding window approach, reducing the number of comparisons.

Disadvantages

  • Worst-Case Complexity: The algorithm might perform poorly in certain cases, resulting in high time complexity.

Rabin-Karp Algorithm Code Explanation

Here's an example of the Rabin-Karp Algorithm implemented in JavaScript:

Sorting-Algo/rbnk.js
function searchRabinKarp(text, pattern) {
    const textLength = text.length;
    const patternLength = pattern.length;
    const prime = 101; // Prime number for hashing
 
    // Hash function to generate the hash value
    function hash(str, length) {
        let hashVal = 0;
        for (let i = 0; i < length; i++) {
            hashVal += str.charCodeAt(i) * Math.pow(prime, i);
        }
        return hashVal;
    }
 
    // Calculate hash values for the text and the pattern
    const textHash = hash(text, patternLength);
    const patternHash = hash(pattern, patternLength);
 
    for (let i = 0; i <= textLength - patternLength; i++) {
        // Check hash values
        if (textHash === patternHash) {
            let match = true;
            for (let j = 0; j < patternLength; j++) {
                if (text[i + j] !== pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                console.log("Pattern found at index", i);
            }
        }
 
        // Recalculate the hash for the next substring
        if (i < textLength - patternLength) {
            textHash = (textHash - text.charCodeAt(i) + text.charCodeAt(i + patternLength)) * prime;
        }
    }
}
 
// Example usage
const text = "AABAACAADAABAABA";
const pattern = "AABA";
searchRabinKarp(text, pattern);
Linear SearchSorting Algorithm