Javascript

Question

我已经使用 node.js 编写了 Boyer-Moore horspool 字符串匹配算法。该程序可以运行，但总是输出 -1，如果模式字符串不在指定文本中，它应该输出 -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();

如有任何帮助，我们将不胜感激。谢谢！

Answer 1

让我们从下面开始：

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

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

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

做你想做的。

带有 t[sPat[j]] 和 t[sText[i]] 的行不会按预期工作，因为 sText[i] 和 sPat[j] return 是字符而不是数字。您可以试试 t[sPat.charCodeAt(j)] 和 t[sText.charCodeAt(i)]。

为了给你一个开始而不会有太大帮助，这里是维基百科上给出的算法的直接实现：

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

Javascript - 字符串匹配错误输出

Javascript - String matching wrong output

algorithm

node.js

boyer-moore