1632
правки
Изменения
м
rollbackEdits.php mass rollback
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <br>(Brute Force algorithm)]]
|<tex>O(p \cdot (t - p))</tex>
|<tex>O(pt^2)</tex>
|
|<tex>O(1)</tex>
|Single
|Прямой
|Сравнение — «чёрный ящик». Если <tex>p</tex> достаточно мало по сравнению с <tex>t</tex>, то асимптотика будет близкой к <tex>O(t)</tex>, что позволяет использовать его на практике в случаях, когда паттерн много меньше текста (например, ctrlCtrl+F в браузерах)
|-align = "center"
|Single
|Прямой
|Использует [[Суффиксный массив]]. Если использовать [[Алгоритм Касаи и др.| Largest common prefix (lcp)]], то можно уменьшить асимптотику до <tex>O(p + \log t)</tex>. Суффиксный массив можно строить[[Построение суффиксного массива с помощью стандартных методов сортировки| стандартными способами]] или [[Алгоритм КаркайненаКарккайнена-Сандерса| алгоритмом КаркайненаКарккайнена-Сандерса]]. Асимптотика приведена для построения суффиксного массива с помощью алгоритма КаркайненаКарккайнена-Сандерса
|-align = "center"
|Прямой
|Позволяет выполнять поиск подстроки в строке за линейное время
|- align = "center"
|[[Алгоритм Апостолико-Крочемора| Алгоритм Апостолико-Крочемора <br>( Apostolico-Crochemore algorithm)]]
|<tex>O(t)</tex>
|<tex>O(t)</tex>
|<tex>O(p)</tex>
|<tex>O(p)</tex>
|Single
|Прямой
|В худшем случае выполнит <tex>\dfrac{3}{2} n</tex> сравнений.
|}
