Алгоритм Бойер Мура

[anoxina]

var badChar = new Array(); // Создаёт массива, где каждой букве шаблона соответствует индекс её последнего вхождения
var answer = new Array(); // Создаёт массива ответов. Тут лежат индексы вхождений слова "война" в текст
var index = 0; // Позиция, на которой находится цикл на данной итерации
var iterCount = st2.length - st.length; // Вычисляет кол-во итераций, чтобы не выйти за пределы строки

for(var j = 0; j < m - 1 ; j++) // Заполняет массив badChar (индексы с единицы, а не с нуля)
badChar[st.charAt(j)] = j + 1 ;


while (index <= iterCount){ // Сам поиск: Выполняется пока index <= длине текста минус длине строки
var pos = m - 1; // Вычисляет позицию последней буквы шаблона
// Вычисляет позицию буквы текста, с которой нужно начинать сравнения

while (st2.charAt(index + pos) == st.charAt(pos)){ // Пока символ строки равен символу текста, и правда, то
if (pos == 0){ // Если длина строки = 0,то добавляем элемент индекса в массив answer
answer.push(index + 1);
}
pos--;
}
if(pos == -1)
index += m; // Если нет, то увеличиваем index на длину шаблона
else if (badChar[st2.charAt(pos + index)] == undefined)
index += pos + 1 // Проверка на то, определён ли символ, с которого начиналось сравнение, в словаре badChar
else
index += Math.max(1,m - badChar[st2.charAt(pos + index)]); // Иначе index увеличиваем на наибольшее значение из (единицы) и (разности длины шаблона и эвристики несовпавшего символа)
}

if (answer.length==0)
WSH.echo("Not found");
else {
WSH.echo("Mathces: " + answer.length);
WSH.echo(answer.join("\n"));
}