Имя пользователя:
Пароль:
 | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » VBS/WSH/JS - Алгоритм Бойер-Мура

Ответить
Настройки темы
VBS/WSH/JS - Алгоритм Бойер-Мура

Новый участник


Сообщения: 3
Благодарности: 0

Профиль | Отправить PM | Цитировать


Код: Выделить весь код
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", а остальное не видит

Отправлено: 10:36, 17-04-2016

 


Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » VBS/WSH/JS - Алгоритм Бойер-Мура

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
Закону Мура исполнилось 50 лет OSZone News Новости железа 1 21-04-2015 11:06
Графеновые наноленты могут продлить жизнь закону Мура OSZone News Новости железа 0 18-02-2014 14:30
IDF 2012: Intel даёт закону Мура ещё десять лет жизни OSZone News Новости информационных технологий 0 17-09-2012 06:30
Закон Мура через десять лет потеряет свою актуальность? OSZone News Новости информационных технологий 1 02-05-2012 13:39
Алгоритм pauluss Программирование и базы данных 1 06-10-2006 10:53




 
Переход