Изменения
Нет описания правки
Пусть у нас есть образец <tex> P </tex>, строка <tex> S </tex> и [[Суффиксный массив|суффиксный массив]] <tex> sufArray </tex>. Мы хотим найти все вхождения данного образца в данную строку. Существует несколько методов решения данной задачи.
==Решение при помощи бинарного поиска==
Понятно, что если образец <tex> P </tex> входит в строку <tex> S </tex>, то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве <tex> sufArray </tex> они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве. <br>
Определим границы, в которых лежат вхождения. Пусть <tex> |S| </tex> - длина строки <tex> S </tex>. Тогда на На первом шаге сравниваем суффикс <tex> sufArray[|S| / 2] </tex> и образец <tex> P </tex>. Если суффикс лексикографически больше, то необходимо идти в левую половину <tex> sufArray </tex>, иначе в правую. На следующем шаге аналогично проверяем суффикс по середине от половины суффискного массива, затем от четверти и так далее. В результате проделанной работы получим левую и правую границы <tex> L </tex> и <tex> R </tex> соответственно. В этих границах и лежат вхождения образца <tex> P </tex> в строку <tex> S </tex>. <br>Время лексикографического сравнения образца <tex> P </tex> с суффиксом <tex> S </tex> равно длине их общего префикса и не превышает может превышать <tex> |SP| </tex>. Поэтому время работы алгоритма равно <tex> O(|SP|log|S|)</tex>. ==Улучшение бинарного поиска==
