RabinKarp.js

/*
 * Implements the Rabin-Karp algorithm for pattern searching.
 *
 * The Rabin-Karp algorithm is a string searching algorithm that uses hashing to find patterns in strings.
 * It is faster than naive string matching algorithms because it avoids comparing every character in the text.
 *
 * This implementation uses a rolling hash function to efficiently compute the hash values of substrings.
 * It also uses a modulo operator to reduce the size of the hash values, which helps to prevent hash collisions.
 *
 * The algorithm returns an array of indices where the pattern is found in the text. If the pattern is not
 * found, the algorithm returns an empty array.
 *
 * [Reference](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)
 */

const BASE = 256 // The number of characters in the alphabet
const MOD = 997 // A prime number used for the hash function

function rabinKarpSearch(text, pattern) {
  const patternLength = pattern.length
  const textLength = text.length
  const hashPattern = hash(pattern, patternLength)
  const hashText = []
  const indices = []

  // Calculate the hash of the first substring in the text
  hashText[0] = hash(text, patternLength)

  // Precompute BASE^(patternLength-1) % MOD
  const basePow = Math.pow(BASE, patternLength - 1) % MOD

  for (let i = 1; i <= textLength - patternLength + 1; i++) {
    // Update the rolling hash by removing the first character
    // and adding the next character in the text
    hashText[i] =
      (BASE * (hashText[i - 1] - text.charCodeAt(i - 1) * basePow) +
        text.charCodeAt(i + patternLength - 1)) %
      MOD

    // In case of hash collision, check character by character
    if (hashText[i] < 0) {
      hashText[i] += MOD
    }

    // Check if the hashes match and perform a character-wise comparison
    if (hashText[i] === hashPattern) {
      if (text.substring(i, i + patternLength) === pattern) {
        indices.push(i) // Store the index where the pattern is found
      }
    }
  }

  return indices
}

function hash(str, length) {
  let hashValue = 0
  for (let i = 0; i < length; i++) {
    hashValue = (hashValue * BASE + str.charCodeAt(i)) % MOD
  }
  return hashValue
}

export { rabinKarpSearch }