Javascript - Zeichenfolge, die falsche Ausgabe

Question

Ich habe Boyer-Moore Horspool String Matching-Algorithmus mit node.js codiert. Das Programm funktioniert, gibt aber immer -1 aus, was es ausgeben soll, wenn die Musterzeichenfolge nicht im angegebenen Text ist.

Ich bin nicht in der Lage, herauszufinden, für das Leben von mir, was nicht funktioniert, und ich wäre sehr dankbar für einen Hinweis auf das, was ich beheben muss.

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

Jede Hilfe wäre sehr dankbar. Danke!

Answer 1

Start Lassen Sie uns von unten unter:

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

nicht bei allen. Die erste Zeile initiiert ein Array mit 256 leeren Einträgen, die zweite Zeile initiiert ein Array mit einem Element: Das Array wird in der darüber liegenden Zeile erstellt. Das ist nicht das, was Sie tun wollten, nehme ich an. So

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

macht was Sie wollen.

Die Linien mit t[sPat[j]] und t[sText[i]] werden nicht wie erwartet funktionieren, weil sText[i] und sPat[j] ein Zeichen anstelle einer Zahl zurück. Sie könnten t[sPat.charCodeAt(j)] und t[sText.charCodeAt(i)] einen Versuch geben.

Ihnen zu viel, einen Anfang zu geben, ohne zu helfen, hier ist eine Straight-Forward-Implementierung des Algorithmus in der Wikipedia gegeben:

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