Изменения

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

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

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

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

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

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

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

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

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

!width="25%"|Название !! width="5%"| Среднее !! width="5%"| Худшее !! width="5%"|Необходимость препроцессинга Препроцессинг !! width="5%"| Дополнительная память !! 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[Z-igm.univфункция| Поиск подстроки в строке с помощью Z-mlv.fr/~lecroq/string/node18.html#SECTION00180 Алгоритм Бойера-Мура-Хорспула <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>

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

|<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>

|[http://www-igm.univ-mlv.fr/~lecroq/string/node6.html#SECTION0060 [Алгоритм Shift-Or algorithm]]|<tex>O(ht)</tex> <br> w — размер машинного слова|<tex>O(h t \cdot ceil(\dfrac{n / }{w)})</tex> <br> <tex> w </tex> — размер машинного слова|Да <br> <tex>O(n p + \sigma)</tex>|<tex>O(n p + \sigma)</tex>

|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= tex>p \leqslant w</tex>. Иначе деградирует и по памяти, и по сложности.

|<tex>O(ht)</tex>|<tex>O(hnpt)</tex>|Да <br> <tex>O(n p + \sigma)</tex>|<tex>O(n p + \sigma)</tex>

|Считается наиболее быстрым из алгоритмов общего назначения. Использует эвристики.Существует большое количество оптимизаций<ref>Например, [http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура <br>(Turbo-BM algorithm)]</ref>

|[http://www-igm.univ-mlv.fr/~lecroq/string/node20.html#SECTION00200 [Алгоритм Чжу-Такаоки поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива <br>(Zhu-Takaoka algorithmSuffix array)]]|<tex>O(hp\log t)</tex>|<tex>O(hnp\log t)</tex>|Да <br> <tex>O(n + \sigma^2t)</tex>|<tex>O(n + \sigma^2t)</tex>

|ОбратныйПрямой|Оптимизация БойераИспользует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(p + \log t)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм Карккайнена-Сандерса| алгоритмом Карккайнена-Сандерса]]. Асимптотика приведена для построения суффиксного массива с помощью алгоритма Карккайнена-Мура под короткие алфавитыСандерса

|[http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150 Турбо-алгоритм Бойера-Мура [Сжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного дерева <br>(Turbo-BM algorithmSuffix tree)]]|<tex>O(hp)</tex>|<tex>O(hp)</tex>|Да <br> <tex>O(n + \sigmat)</tex>|<tex>O(n + \sigmat)</tex>

|ОбратныйПрямой|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений Позволяет выполнять поиск подстроки в худшем случае. Количество эвристик увеличивается до трёх.строке за линейное время

|-align = "center"|[[Алгоритм поиска подстроки в строке с помощью суффиксного массиваАпостолико-Крочемора| Алгоритм Апостолико-Крочемора <br>( Apostolico-Crochemore algorithm)]]|<tex>O(nlog(h)t)</tex>|<tex>O(nlog(h)t)</tex>|Да <br> <tex>O(np)</tex>|<tex>O(nlog^2(n)p)</tex>

|Прямой|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до В худшем случае выполнит <tex>O(\dfrac{3}{2} n + log(h))</tex>сравнений.

== Ссылки Примечания == <references /> == Источники информации ==

* [[wikipediaWikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] {{---}} Очень много — (англ.) Большое количество разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.