Изменения

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

Во всех алгоритмах этого типа сравнение является черным ящиком «чёрным ящиком» для программиста.  Преимущества:* + Позволяет позволяет использовать стандартные функции сравнения участков памяти (man *cmp(3)), которые, зачастую, оптимизированы под конкретное железо.  Недостатки:* - Не не выдается точка, в которой произошло несовпадение.

==== Прямой ====Недостатки:* + Отсутсвие регрессии на «плохих» данных.* - Не не самая хорошая средняя ассимптотическая асимптотическая сложность.

Паттерн движется по тексту слева на правонаправо, но сравнение подстрок происходит с права на левосправа налево. Преимущества:* + При при несовпадении позволяет перемещать паттерн по строке сразу на несколько символов. Недостатки:* производительность сильно зависит от данных.

Специфические алгоритмы, основанные, как правило, на некоторых эмпирических наблюдениях над словарём. <ref>Например, [[Wikipedia:en:Raita Algorithm| Алгоритм Райты (англ.)]]</ref>

#Один Сколько поисковых шаблонов может обработать алгоритм за один раз. * один шаблон (англ. ''Single single pattern algorithms'')#Конечное * конечное количество шаблонов (англ. ''finite set of patterns'')#Бесконечное * бесконечное количество шаблонов (Регулярные грамматики/regexpангл. ''infinite number of patterns'ы') (см. [[Теория формальных языков]])

*[[Суффиксный_массивСуффиксный массив]]

*<tex>|haystacktext| = ht</tex> — длина текста*<tex>|needlepattern| = np</tex> — длина паттерна

*<tex>m</tex> — суммарная длина всх всех паттернов

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

|<tex>O(n p \cdot (h t - np))</tex>|<tex>O(nt^2)</tex>|Нет

|Сравнение — «чёрный ящик». Если <tex>np</tex> достаточно мало по сравнению с <tex>ht</tex>, то ассимптотика асимптотика будет близкой к <tex>O(ht)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrlCtrl+F в браузерах)

|- align = "center"|[http://www-igm.univ[Z-mlv.fr/~lecroq/string/node18.html#SECTION00180функция| Алгоритм БойераПоиск подстроки в строке с помощью Z-Мура-Хорспула <br>(Horspool algorithm)функции]]|<tex>O(nht)</tex>|<tex>O(nht)</tex>|Да <br> <tex>O(n p + \sigmat)</tex>|<tex>O(\sigmap)</tex>

|В самой простой реализации использует только эвристику стоп-символа и относится к алгоритмом с сравнением — «чёрным ящиком».  

|<tex>O(n p + ht)</tex>|<tex>O(nhpt)</tex>|Да <br> <tex>O(np)</tex>

|Single/ Finite

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

|<tex>O(n p + ht)</tex>|<tex>O(n p + ht)</tex>|Да <br> <tex>O(np)</tex>|<tex>O(np)</tex>

|<tex>O(m + h t + a)</tex>|<tex>O(ht)</tex>|Да <br> <tex>O(m)</tex>

|finiteFinite|Прямой|Строит конечный автомат. Можно хранить таблицу переходов как индексный массив (array), а можно как [[Красно-черное дерево]]. В последнем случае уменьшится расход памяти, но ухудшится асимптотика |-align = "center"|[[Алгоритм Shift-Or]]|<tex>O(t)</tex>|<tex>O(t \cdot \dfrac{n}{w})</tex> <br> <tex>w</tex> — размер машинного слова|<tex>O(p + \sigma)</tex>|<tex>O(p + \sigma)</tex>|Single|Прямой|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если <tex>p \leqslant w</tex>. Иначе деградирует и по памяти, и по сложности |-align = "center"|[[Алгоритм Бойера-Мура| Алгоритм Бойера-Мура <br>(Boyer-Moore algorithm)]]|<tex>O(t)</tex>|<tex>O(pt)</tex>|<tex>O(p + \sigma)</tex>|<tex>O(p + \sigma)</tex>|Single|Обратный|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики. Существует большое количество оптимизаций<ref>Например, [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура <br>(Turbo-BM algorithm)]</ref> |-align = "center"|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива <br>(Suffix array)]]|<tex>O(p\log t)</tex>|<tex>O(p\log t)</tex>|<tex>O(t)</tex>|<tex>O(t)</tex>|Single|Прямой|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(p + \log t)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]]. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Карккайнена-Сандерса |-align = "center"|[[Сжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного дерева <br>(Suffix tree)]]|<tex>O(p)</tex>|<tex>O(p)</tex>|<tex>O(t)</tex>|<tex>O(t)</tex>|Single|Прямой|Позволяет выполнять поиск подстроки в строке за линейное время |- align = "center"|[[Алгоритм Апостолико-Крочемора| Алгоритм Апостолико-Крочемора <br>( Apostolico-Crochemore algorithm)]]|<tex>O(t)</tex>|<tex>O(t)</tex>|<tex>O(p)</tex>|<tex>O(p)</tex>|Single

|Строит конечный автоматВ худшем случае выполнит <tex>\dfrac{3}{2} n</tex> сравнений.