34
правки
Изменения
add Z-function and suffix tree
|Прямой
|Сравнение — «чёрный ящик». Если <tex>n</tex> достаточно мало по сравнению с <tex>h</tex>, то ассимптотика будет близкой к O(h), что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrl+F в браузерах)
|-align = "center"
|[[Z-функция| Поиск подстроки в строке с помощью Z-функции]]
|<tex>O(h)</tex>
|<tex>O(h)</tex>
|<tex>O(h + n)</tex>
|<tex>O(h + n)</tex>
|Single
|Прямой
|Сам алгоритм поиска описан на [http://e-maxx.ru/algo/z_function#7 e-maxx.ru:z-function]
|- align = "center"
|Прямой
|Использует [[Префикс-функция| префикс-функцию]]
|-align = "center"
|[[Алгоритм Колусси| Алгоритм Колусси <br>(Colussi algorithm)]]
|<tex>O(h)</tex>
|<tex>O(h)</tex>
|<tex>O(n)</tex>
|<tex>O(n)</tex>
|Single
|Прямой / Обратный
|Оптимизация [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-Пратта]] использует как прямой, так и обратный обход
|- align = "center"
|-align = "center"
|[[Алгоритм поиска подстроки в строке с помощью суффиксного массива| Поиск подстроки в строке с помощью суффиксного массива <br>(Suffix array)]]
|<tex>O(n\log h)</tex>
|<tex>O(n\log h)</tex>
|<tex>O(nh)</tex>|<tex>O(n\log^2 nh)</tex>
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно увеличить асимптотику до <tex>O(n + log(h))</tex>. Суффиксный массив строится [[Алгоритм Каркайнена-Сандерса| алгоритмом Каркайнена-Сандерса]]
|-align = "center"
|[[Алгоритм КолуссиСуффиксный бор| Алгоритм Колусси Поиск подстроки в строке с помощью суффиксного бора <br>(Colussi algorithmSuffix tree)]]|<tex>O(h)</tex>|<tex>O(h)</tex>
|<tex>O(n)</tex>
|<tex>O(n)</tex>
|<tex>O(h^2)</tex>
|<tex>O(h^2)</tex>
|Single
|Прямой / Обратный|Оптимизация Можно использовать [[Алгоритм Кнута-Морриса-Пратта| Алгоритма Кнута-Морриса-ПраттаСжатое суффиксное дерево]] использует как прямой, так и обратный обходдля оптимизации расхода памяти
|}
