Изменения
→Сравнение алгоритмов
'''Поиск подстроки в строке''' (англ. ''String searching algorithm'') — класс алгоритмов над строками, которые позволяют найти паттерн (''needlepattern'') в тексте (''haystacktext'').
== Классификация алгоритмов поиска подстроки в строке ==
Во всех алгоритмах этого типа сравнение является «чёрным ящиком» для программиста.
=== По порядку сравнения паттерна в тексте ===
==== Прямой ====
* отсутствие регрессии на «плохих» данных.
* не самая хорошая средняя асимптотическая сложность.
==== Обратный ====
Паттерн движется по тексту слева направо, но сравнение подстрок происходит справа налево.
==== Сравнение в необычном порядке ====
|[[Наивный алгоритм поиска подстроки в строке| Наивный алгоритм <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> сравнений.
|}
