Skip to content

Instantly share code, notes, and snippets.

@derek

derek/gist:8035740

Last active April 30, 2018 04:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save derek/8035740 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save derek/8035740 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. derek revised this gist Dec 19, 2013. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions gistfile1.js
    View file
    Original file line number Diff line number Diff line change
    @@ -4,10 +4,10 @@ function boyer_moore_horspool(haystack, needle) {
    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
    needle.split('').forEach(function (char, i) {
    Array.prototype.forEach.call(needle, function (char, i) {
    badMatchTable[char] = last - i;
    });

  2. derek revised this gist Dec 19, 2013. 1 changed file with 25 additions and 24 deletions.
    49 changes: 25 additions & 24 deletions gistfile1.js
    View file
    Original file line number Diff line number Diff line change
    @@ -1,30 +1,31 @@
    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 ahead when a comparison fails
    needle.split('').forEach(function (char, i) {
    badMatchTable[char] = last - i;
    });

    // Now find the string
    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;
    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
    needle.split('').forEach(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;
    }

    offset += badMatchTable[haystack[offset + last]] || last;
    }

    return -1;

    return -1;
    }

    var stringLocation = boyer_moore_horspool('because sometimes algorithms are more fun than str.search()', 'algorithms');
  3. derek revised this gist Dec 19, 2013. 1 changed file with 2 additions and 1 deletion.
    3 changes: 2 additions & 1 deletion gistfile1.js
    View file
    Original file line number Diff line number Diff line change
    @@ -13,7 +13,8 @@ function boyer_moore_horspool(haystack, needle) {

    // Now find the string
    while (offset <= maxOffset) {
    // Search right-to-left, checking to see if the current offset at needle and haystack match. If they do, repeat, and if we match the first character, return the offset.
    // 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;
  4. derek created this gist Dec 19, 2013.
    31 changes: 31 additions & 0 deletions gistfile1.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,31 @@
    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 ahead when a comparison fails
    needle.split('').forEach(function (char, i) {
    badMatchTable[char] = last - i;
    });

    // Now find the string
    while (offset <= maxOffset) {
    // Search right-to-left, checking to see if the current offset at needle and haystack match. If they do, repeat, and if we 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);