Search Substring Boyer Moore Horspool

Benchmark created by Stephen Keep on October 16, 2014

Setup

var haystack = 'because sometimes algorithms are more fun than str.search()',
        needle = 'algorithms';
    
    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;
    }

Test runner

var stringLocation = haystack.indexOf(needle);
console.log(stringLocation);

var stringLocation = boyer_moore_horspool(haystack, needle); 
console.log(stringLocation);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by Stephen Keep on October 16, 2014