2

我已经使用 node.js 编写了 Boyer-Moore horspool 字符串匹配算法。该程序工作，但总是输出 -1，如果模式字符串不在指定文本中，它应该输出。

我终其一生都无法弄清楚什么是行不通的，我会非常感谢提示我需要解决的问题。

我的代码

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();

任何帮助将不胜感激。谢谢你！

4

1 回答 1

1

让我们从下面开始：

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

根本不起作用。第一行初始化一个包含 256 个空条目的数组，第二行初始化一个包含一个元素的数组：数组构建在上面的行中。我想这不是你想做的。所以

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

做你想做的事。

带有t[sPat[j]]and的行t[sText[i]]不会按预期工作，因为sText[i]andsPat[j]返回的是字符而不是数字。你可以t[sPat.charCodeAt(j)]试一试t[sText.charCodeAt(i)]。

为了让您在不提供太多帮助的情况下开始，这里是 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();
于 2016-05-22T03:46:40.100 回答