Изменения

\''Поиск подстроки в строке'' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''needle'') в тексте (''haystack'').

Во всех алгоритмах этого типа сравнение является черным ящиком «чёрным ящиком» для программиста.

* - Не самая хорошая средняя ассимптотическая асимптотическая сложность.

Паттерн движется по тексту слева на право, но сравнение подстрок происходит с права справа на лево.

#Бесконечное количество шаблонов (Регулярные грамматики''infinite number of patterns'') (см. [[Теория формальных языков]], [http://en.wikipedia.org/wiki/Regular_expression regexp'ы])

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

!width="25%"|Название !! width="85%"| Среднее !! width="85%"| Худшее !! width="85%"|Необходимость препроцессинга !! width="85%"| Дополнительная память !! width="10%"| Кол-во поисковых шаблонов !! width="10%"| Порядок сравнения !! width="35%"| Описание

|[http://www-igm.univ-mlv.fr/~lecroq/string/node18.html#SECTION00180| Алгоритм Бойера-Мура-Хорспула <br>(Horspool algorithm)]

|Single/ Finite

|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов.

|finiteFinite|Прямой|Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как [[Красно-черное дерево]]. В последнем случае уменьшится расход памяти, но ухудшится асимптотика |-align = "center"|[http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060 Shift-Or algorithm]|<tex>O(h)</tex> <br> w — размер машинного слова|<tex>O(h \cdot ceil(n / w))</tex> <br> w — размер машинного слова|Да <br> <tex>O(n + \sigma)</tex>|<tex>O(n + \sigma)</tex>|Single

|Строит конечный автоматИспользует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= w. Иначе деградирует и по памяти, и по сложности. |-align = "center"|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура <br>(Boyer-Moore algorithm)]]|<tex>O(h)</tex>|<tex>O(hn)</tex>|Да <br> <tex>O(n + \sigma)</tex>|<tex>O(n + \sigma)</tex>|Single|Обратный|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. |-align = "center"|[http://www-igm.univ-mlv.fr/~lecroq/string/node20.html#SECTION00200 Алгоритм Чжу-Такаоки <br>(Zhu-Takaoka algorithm)]|<tex>O(h)</tex>|<tex>O(hn)</tex>|Да <br> <tex>O(n + \sigma^2)</tex>|<tex>O(n + \sigma^2)</tex>|Single|Обратный|Оптимизация Бойера-Мура под короткие алфавиты |-align = "center"|[http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура <br>(Turbo-BM algorithm)]|<tex>O(h)</tex>|<tex>O(h)</tex>|Да <br> <tex>O(n + \sigma)</tex>|<tex>O(n + \sigma)</tex>|Single|Обратный|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений в худшем случае. Количество эвристик увеличивается до трёх. |-align = "center"|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]|<tex>O(nlog(h))</tex>|<tex>O(nlog(h))</tex>|Да <br> <tex>O(n)</tex>|<tex>O(nlog^2(n))</tex>|Single||Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>