const fc = require('fast-check');
/**
* A prime number used to create
* the hash representation of a word
*
* Bigger the prime number,
* bigger the hash value
*/
const PRIME = 97;
/**
* Function that creates hash representation of the word.
*
* @param {string} word
* @return {number}
*/
function hashWord(word) {
let hash = 0;
let primePower = 1;
for (let charIndex = 0; charIndex < word.length; charIndex += 1) {
hash += word[charIndex].charCodeAt(0) * primePower;
primePower = (primePower * PRIME) | 0;
}
return hash | 0;
}
/**
* Function that creates hash representation of the word
* based on previous word (shifted by one character left) hash value.
*
* Recalculates the hash representation of a word so that it isn't
* necessary to traverse the whole word again
*
* @param {number} prevHash
* @param {string} prevWord
* @param {string} newWord
* @return {number}
*/
function reHashWord(prevHash, prevWord, newWord) {
const newWordLastIndex = newWord.length - 1;
let primePower = 1;
for (let charIndex = 0; charIndex < newWordLastIndex; ++charIndex) {
primePower = (primePower * PRIME) | 0;
}
let newHash = prevHash - prevWord[0].charCodeAt(0);
newHash /= PRIME;
newHash += newWord[newWordLastIndex].charCodeAt(0) * primePower;
return newHash | 0;
}
/**
* @param {string} text
* @param {string} word
* @return {number}
*/
function rabinKarp(text, word) {
// Calculate word hash that we will use for comparison with other substring hashes.
const wordHash = hashWord(word);
let prevSegment = null;
let currentSegmentHash = null;
// Go through all substring of the text that may match
for (let charIndex = 0; charIndex <= text.length - word.length; charIndex += 1) {
const currentSegment = text.substring(charIndex, charIndex + word.length);
// Calculate the hash of current substring.
if (currentSegmentHash === null) {
currentSegmentHash = hashWord(currentSegment);
} else {
currentSegmentHash = reHashWord(currentSegmentHash, prevSegment, currentSegment);
}
prevSegment = currentSegment;
// Compare the hash of current substring and seeking string.
if (wordHash === currentSegmentHash) {
// In case if hashes match let's check substring char by char.
let numberOfMatches = 0;
for (let deepCharIndex = 0; deepCharIndex < word.length; deepCharIndex += 1) {
if (word[deepCharIndex] === text[charIndex + deepCharIndex]) {
numberOfMatches += 1;
}
}
if (numberOfMatches === word.length) {
return charIndex;
}
}
}
return -1;
}
// Failure for seed = 1532431675150: [" "," !",""]
console.log(hashWord(" !"));
console.log(reHashWord(hashWord(" "), " ", " !"));
// for any strings a, b and c
// rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
fc.assert(
fc.property(
fc.string(), fc.string(), fc.string(),
(a, b, c) => rabinKarp(a + b + c, b) !== -1
)
);
no comments
sign in to comment