DEV Community

ZeeshanAli-0704
ZeeshanAli-0704

Posted on • Updated on

Rabin-Karp in JavaScript

Check if two string are same:

const areStringEqual = function (firstString, secondString) {
  if (firstString !== secondString) {
    return false;
  }
  for (let i = 0; i < firstString.length; i++) {
    if (firstString[i] !== secondString[i]) {
      return false;
    }
  }
  return true;
};
Enter fullscreen mode Exit fullscreen mode

Hash creating logic


const calculateHash = function (myText, largePrime, randomNumber) {
  let hash = 0;
  for (let i = 0; i <= myText.length - 1; i++) {
    hash = (hash * randomNumber + myText.charCodeAt(i)) % largePrime;
  }
  return hash;
};
Enter fullscreen mode Exit fullscreen mode

Search Text using Functions

const searchText = function (sentence, stringToSearch) {
  let largePrime = 337;
  let randomNumber = 50;
  let stringPositions = [];
  let stringToSearchHash = calculateHash(
    stringToSearch,
    largePrime,
    randomNumber
  );
  let text;
  let sentenceHash;
  // Loop through our sentence
  for (let i = 0; i <= sentence.length - stringToSearch.length; i++) {
    text = sentence.slice(i, i + stringToSearch.length);
    sentenceHash = calculateHash(text, largePrime, randomNumber);
// If the hash is not same, then continue to next step
    if (stringToSearchHash !== sentenceHash) continue;


    if (areStringEqual(text, stringToSearch)) {
      stringPositions.push({ position: i });
    }

  }
  return stringPositions;
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)