Изменения
Нет описания правки
Понятно, что если образец <tex> P </tex> входит в строку <tex> S </tex>, то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве <tex> sufArray </tex> они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве. <br>
Определим границы, в которых лежат вхождения. Пусть <tex> length |S| </tex> - длина строки <tex> S </tex>. Тогда на первом шаге сравниваем суффикс <tex> sufArray[length |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> |S| </tex>. Поэтому время работы алгоритма равно <tex> O(|S|log|S|).
