34
правки
Изменения
Нет описания правки
=== По количеству поисковых шаблонов ===
Сколько поисковых шаблонов может обработать алгоритм за один раз.
#Один шаблон (''Single pattern algorithms'')
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>n</tex> достаточно мало по сравнению с <tex>h</tex>, то ассимптотика асимптотика будет близкой к <tex>O(h)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
|-align = "center"
|Single
|Прямой
|Можно модифицировать для поиска подстроки<ref>[http://e-maxx.ru/algo/z_function#7| e-maxxMAXimal :: algo ::Z-functionфункция строки и её вычисление :: Поск подстроки в строке]</ref>
|- align = "center"
|[[Алгоритм Shift-Or]]
|<tex>O(h)</tex>
|<tex>O(h \cdot ceil(\dfrac{n / }{w)})</tex> <br> <tex>w</tex> — размер машинного слова
|<tex>O(n + \sigma)</tex>
|<tex>O(n + \sigma)</tex>
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(n + \log h)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм Каркайнена-Сандерса| алгоритмом Каркайнена-Сандерса]]. Асимптотика приведена для построения Каркайненаномсуффиксного массива с помощью алгоритма Каркайнена-СандерсомСандерса
|-align = "center"
|<tex>O(n)</tex>
|<tex>O(n)</tex>
|<tex>O(h^2)</tex>
|<tex>O(h)</tex>
|Single
|Прямой
|Можно модифицировать для поиска Позволяет выполнять поиск подстрокив строке за линейное время
|}
