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

Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

 

 

23. Сортировки – общая классификация.

Сортировка – упорядочение элементов множества по возрастанию или убыванию

Классификация алгоритмов сортировки

Устойчивость — устойчивая сортировка не меняет взаимного расположения равных элементов.

Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь различают сортировку массивов записей, целиком расположенных в основной памяти (внутреннюю сортировку), и сортировку файлов, хранящихся во внешней памяти и не помещающихся полностью в основной памяти (внешнюю сортировку). Для внутренней и внешней сортировки требуются существенно разные методы.

Также алгоритмы классифицируются по:

потребности в дополнительной памяти или её отсутствии

потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой

Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа сортировки и число перестановок элементов массива.

Простые методы сортировки – выбором, пузырьковая, вставками

Улучшенные – Шелла, Хоара, слиянием