418
правок
Изменения
Нет описания правки
}
}
==Сравнение с другими алгоритмами==
===Достоинства===
* Алгоритм Бойера-Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.
* Алгоритм проще большинства алгоритмов поиска (при некоторых реализациях объем кода сравним с наивным поиском)
* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не походит, т.к. длина шаблона должна быть известна заранее).
===Недостатки===
* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
* Сравнение не является "чёрным ящиком", поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу оптимизатора, либо вручную оптимизировать поиск.
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
* На искусственно подобранных неудачных текстах (например, needle=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается.
==Ссылки==
