Dazzler Dazzler - 6 months ago 26
Node.js Question

Javascript - String matching wrong output

I have coded Boyer-Moore horspool string matching algorithm using node.js. The program works, but always outputs -1, which is what it should output if the pattern string is not in the specified text.

I am unable to figure out for the life of me what isn't working, and I would be most appreciative of a hint for what I need to fix.

My code

var horsPool = function(sText,sPattern)
{
var m = sPattern.length;
var n = sText.length;
var i = m - 1;

while(i<=n-1)
{
var k = 0;
while ((k <= m) && (sPattern[m - 1 - k]) == sText[i - k])
{
k++;
}

if(k==m)
{
return (i - m + 1);
}
else
{
i += t[sText[i]];
}
}
return -1;
}

var shiftTable = function (sPat)
{
var i;
var j;
var m;

m = sPat.length;

for(i=0; i < MAX; i++)
{
t[i] = m;
}

for (j = 0; j<m-2; j++)
{
t[sPat[j]] = m-1 -j;
}
}

var program = function()
{
var text = 'lklkababcabab';
var pattern = 'ka';
shiftTable(pattern);
var pos = horsPool(text,pattern);
if(pos >= 0)
console.log('Pattern found in %d',pos);
else
console.log('Pattern not found');
}

var MAX = new Array(256);
var t = [MAX];

program();


Any help would be greatly appreciated. Thank You!

Answer

Let's start from down under:

var MAX = new Array(256);
var t = [MAX];

does not work at all. The first line initiates an array with 256 empty entries, the second line initiates an array with one element: the array build in the line above. That's not what you wanted to do, I presume. So

var MAX = 256;
var t = new Array(MAX);

does what you want.

The lines with t[sPat[j]] and t[sText[i]] will not work as expected, because sText[i] and sPat[j] return a character instead of a number. You might give t[sPat.charCodeAt(j)] and t[sText.charCodeAt(i)] a try.

To give you a start without helping too much, here is a straight-forward implementation of the algorithm given at Wikipedia:

var horsPool = function (haystack, needle)
{
  var nl = needle.length;
  var hl = haystack.length;
  var skip = 0;
  while (hl - skip >= nl)
  {
    var i = nl - 1;
    while (haystack[skip + i] == needle[i])
    {
      if (i == 0) {
        return skip;
      }
      i--;
    }
    skip = skip + t[haystack.charCodeAt(skip + nl - 1)];
  }
  return - 1;
}
var shiftTable = function (pattern)
{
  for (var i = 0; i < MAX; i++) {
    t[i] = pattern.length;
  }
  for (var i = 0; i < pattern.length - 1; i++) {
    t[pattern.charCodeAt(i)] = pattern.length - 1 - i;
  }
}
var program = function ()
{
  var text = 'lklkababcabab';
  var pattern = 'kab';
  shiftTable(pattern);
  var pos = horsPool(text, pattern);
  if (pos >= 0)
  console.log('Pattern found in %d', pos);
   else
  console.log('Pattern not found');
}
var MAX = 256;
var t = new Array(256);
program();