Изменения

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

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

|Сам алгоритм Можно модифицировать для поиска описан на [http://e-maxxподстроки.ru/algo/z_function#7 e-maxx.ru:z-function]

|<tex>O(h)</tex> <br> w — размер машинного слова|<tex>O(h \cdot ceil(n / w))</tex> <br> <tex> w </tex> — размер машинного слова

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

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

|[[Суффиксный борСжатое суффиксное дерево| Поиск подстроки в строке с помощью суффиксного бора дерева <br>(Suffix tree)]]

|<tex>O(h^2)</tex>

|Можно использовать [[Сжатое суффиксное дерево]] модифицировать для оптимизации расхода памятипоиска подстроки