Изменения

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