Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Алгоритм Бойер-Мура (http://forum.oszone.net/showthread.php?t=313953)

kudrjavcev 17-04-2016 10:36 2627069

Алгоритм Бойер-Мура
 
Код:

var fso = new ActiveXObject("Scripting.FileSystemObject");
var r = fso.OpenTextFile("in.txt", 1, true);
var st = r.ReadLine();                                                      // Считывает первую строку
var st2 = r.ReadAll();                                                      // Считывает весь оставшийся текст
r.Close();

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

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


while (index <= iterCount){                                                // Сам поиск: Выполняется пока index <= длине текста минус длине строки
        var pos = st.length - 1;                                                // Вычисляет позицию последней буквы шаблона
    var ppi = pos + index;                                                  // Вычисляет позицию буквы текста, с которой нужно начинать сравнения
        var flag = false;
   
        while (st.charAt(pos) == st2.charAt(ppi) && !flag){                    // Пока символ строки равен символу текста, и правда, то
                if (pos == 0){                                                      // Если длина строки = 0,то добавляем элемент индекса в массив answer
                        answer.push(index);
                        flag = true;
                }
                pos--;
        ppi--;
        }

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

}

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

Код рабочий, но есть одна проблема, то что я не пойму когда в тексте ищешь допустим "aaa" , то в тексте "aaaaaaaaa" он находит только первые "aaa", а остальное не видит


Время: 13:29.

Время: 13:29.
© OSzone.net 2001-