271
правка
Изменения
Нет описания правки
|ssissippi
|3
|}
== Способы поиска ==
=== Простейший поиск подстроки ===
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так до конца символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за <tex> O(log|s|) </tex>, а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы <tex> O(|p|log|s|)</tex>.
