34
правки
Изменения
small decor changes
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.
=== По порядку сравнения паттерна в тексте ===
==== Прямой ====
==== Обратный ====
Паттерн движется по тексту слева на право, но сравнение подстрок происходит справа на лево.
==== Сравнение в необычном порядке ====
#Один шаблон (''Single pattern algorithms'')
#Конечное количество шаблонов (''finite set of patterns'')
#Бесконечное количество шаблонов (''infinite number of patterns'') (см. [[Теория формальных языков]], [http://en.wikipedia.org/wiki/Regular_expression regexp])
=== По необходимости препроцессинга текста ===
*[[Z-функция]]
*[[Бор]]
*[[Суффиксный_массивСуффиксный массив]]
Алгоритмы использующие препроцессинг — одни из самых быстрых в этом классе.
*<tex>|needle| = n</tex> — длина паттерна
*<tex>a</tex> — размер ответа(кол-во пар)
*<tex>m</tex> — суммарная длина всх всех паттернов
{|class="wikitable"
|<tex>O(n \cdot (h - n))</tex>
|<tex>O(n^2)</tex>
|Нет
|<tex>O(1)</tex>
|Single
|<tex>O(nh)</tex>
|<tex>O(nh)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
|<tex>O(\sigma)</tex>
|Single
|<tex>O(n + h)</tex>
|<tex>O(nh)</tex>
|Да <br> <tex>O(n)</tex>
|<tex>O(1)</tex>
|Single / Finite
|<tex>O(n + h)</tex>
|<tex>O(n + h)</tex>
|Да <br> <tex>O(n)</tex>
|<tex>O(n)</tex>
|Single
|<tex>O(m + h + a)</tex>
|<tex>O(h)</tex>
|Да <br> <tex>O(m)</tex>
|<tex>O(m\sigma)</tex>
|Finite
|<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
|<tex>O(h)</tex>
|<tex>O(hn)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
|<tex>O(n + \sigma)</tex>
|Single
|<tex>O(h)</tex>
|<tex>O(hn)</tex>
|Да <br> <tex>O(n + \sigma^2)</tex>
|<tex>O(n + \sigma^2)</tex>
|Single
|<tex>O(h)</tex>
|<tex>O(h)</tex>
|Да <br> <tex>O(n + \sigma)</tex>
|<tex>O(n + \sigma)</tex>
|Single
|-align = "center"
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
|<tex>O(nlog(n\log h))</tex>|<tex>O(nlog(n\log h))</tex>|Да <br> <tex>O(n)</tex>|<tex>O(nlogn\log^2(n))</tex>
|Single
|
== Ссылки ==
* [[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
* [[wikipediaWikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] {{---}} — (англ.) Очень много разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
