Javascript - Строка, соответствующая неправильному выходу

Question

Я закодировал алгоритм соответствия строки хорваля Boyer-Moore, используя node.js. Программа работает, но всегда выводит -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();