Skip to content

Instantly share code, notes, and snippets.

@derek
Last active April 30, 2018 04:01
Show Gist options
  • Star 7 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save derek/8035740 to your computer and use it in GitHub Desktop.
Save derek/8035740 to your computer and use it in GitHub Desktop.
Boyer–Moore–Horspool in JavaScript
function boyer_moore_horspool(haystack, needle) {
var badMatchTable = {};
var maxOffset = haystack.length - needle.length;
var offset = 0;
var last = needle.length - 1;
var scan;
// Generate the bad match table, which is the location of offsets
// to jump forward when a comparison fails
Array.prototype.forEach.call(needle, function (char, i) {
badMatchTable[char] = last - i;
});
// Now look for the needle
while (offset <= maxOffset) {
// Search right-to-left, checking to see if the current offset at
// needle and haystack match. If they do, rewind 1, repeat, and if we
// eventually match the first character, return the offset.
for (scan=last; needle[scan] === haystack[scan+offset]; scan--) {
if (scan === 0) {
return offset;
}
}
offset += badMatchTable[haystack[offset + last]] || last;
}
return -1;
}
var stringLocation = boyer_moore_horspool('because sometimes algorithms are more fun than str.search()', 'algorithms');
console.log(stringLocation);
@mghifariyusuf
Copy link

this code is not active again?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment