34
правки
Изменения
add Colussi algorithm and some fixes
|Single / Finite
|Прямой
|Данный алгоритм использует хэширование, что снижает скорость в среднем. Можно модифицировать для поиска нескольких паттернов.
|- align = "center"
|-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 — размер машинного слова
|Single
|Прямой
|Использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. Эффективен, если n <= w. Иначе деградирует и по памяти, и по сложности.
|-align = "center"
|Single
|Обратный
|Не дает регрессии на «плохих» данных. <tex>2h</tex> сравнений в худшем случае. Количество эвристик увеличивается до трёх.
|-align = "center"
|<tex>O(n\log^2 n)</tex>
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix(lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>
|-align = "center"
|[[Алгоритм Колусси| Алгоритм Колусси <br>(Colussi algorithm)]]
|<tex>O(h)</tex>
|<tex>O(h)</tex>
|<tex>O(n)</tex>
|<tex>O(n)</tex>
|Single
|Прямой / Обратный
|Оптимизация [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-Пратта]] использует как прямой, так и обратный обход
|}
* [[wikipedia:ru:Поиск_подстроки | Википедия {{---}} Поиск подстроки]]
* [[Wikipedia:en:String_searching_algorithm | Википедия {{---}} String searching algorithm]]
* [http://www-igm.univ-mlv.fr/~lecroq/string/index.html ESMAJ] — (англ.) Очень много Большое количество разных алгоритмов поиска подстроки в строке. Многие из них в данной статье не описаны.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
