Javascript – string匹配错误的输出

我使用node.js编码了Boyer-Moore horspoolstring匹配algorithm。 该程序工作，但总是输出-1，这是它应该输出，如果模式string不在指定的文本。

我无法弄清楚什么是不正常的工作，对于我需要解决的问题，我会非常感激。

我的代码

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个空条目初始化一个数组，第二行用一个元素初始化一个数组：第一行在上面的行中构build数组。 我想这不是你想要做的。 所以

 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)] 。

为了给你一个没有太多帮助的开始，这里是维基百科给出的algorithm的直接实现：

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