Rabin-Karp

The Rabin-Karp algorithm is a string searching algorithm that efficiently finds patterns within a text using hashing.

It's particularly useful when you need to find multiple patterns in a single text.

Here's an overview of how it works:

1. Hashing: The algorithm uses a hash function to generate a hash value for each substring of the text and the pattern to be searched.

2. Comparing Hashes: It compares the hash values of the pattern and each substring of the text. If the hash values match, it performs a full comparison of the substring and the pattern to confirm the match.

3. Rolling Hash: Instead of recalculating the hash for each substring, it uses a rolling hash function to efficiently update the hash value as it moves through the text.

pseudocode:

function RabinKarp(string s, string pattern):
    n <- length(s)
    m <- length(pattern)
    patternHash <- hash(pattern)  // Compute hash value of pattern
    hash <- hash(s[1:m])          // Compute hash value of the first substring of length m

    for i from 0 to n - m:
        if hash == patternHash and s[i:i+m-1] == pattern:
            return i                // Pattern found at position i
        if i < n - m:
            hash <- updateHash(hash, s[i], s[i+m])  // Update hash value for the next substring

    return -1                       // Pattern not found

function hash(string s):
    // Compute hash value of a string using a suitable hash function
    // For Rabin-Karp, a simple hash function like polynomial rolling hash can be used

function updateHash(hash, oldChar, newChar):
    // Update hash value based on the removal of oldChar and addition of newChar
    // For Rabin-Karp, a rolling hash update is typically used

function rabinKarp(text, pattern) {
    const prime = 101; // A prime number for hashing
    const patternLength = pattern.length;
    const textLength = text.length;
    const hashPattern = hash(pattern, patternLength); // Hash value for the pattern
    let hashText = hash(text, patternLength); // Hash value for the initial substring of text

    for (let i = 0; i <= textLength - patternLength; i++) {
        if (hashPattern === hashText && text.substring(i, i + patternLength) === pattern) {
            console.log("Pattern found at index", i);
        }
        if (i < textLength - patternLength) {
            hashText = recalculateHash(text, i, i + patternLength, hashText, patternLength, prime);
        }
    }
}

// Function to calculate hash value for a string
function hash(str, length) {
    let hashValue = 0;
    for (let i = 0; i < length; i++) {
        hashValue += str.charCodeAt(i) * Math.pow(10, length - i - 1);
    }
    return hashValue;
}

// Function to recalculate hash value using rolling hash
function recalculateHash(text, oldIndex, newIndex, oldHash, patternLength, prime) {
    let newHash = oldHash - text.charCodeAt(oldIndex);
    newHash = newHash / 10;
    newHash += text.charCodeAt(newIndex) * Math.pow(10, patternLength - 1);
    return newHash;
}

// Example usage
const text = "ABCCDDAEFG";
const pattern = "CDD";
rabinKarp(text, pattern);

In this example, the rabinKarp function takes the text and pattern as inputs and iterates through the text to find occurrences of the pattern.

It uses the hash function to calculate the hash values for the pattern and substrings of the text, and recalculateHash function to update the hash value as it moves through the text.

Finally, it prints the indices where the pattern is found.