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

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