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]返回一个字符而不是数字。您可以试试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();