Алгоритм поиска подстроки в строке с помощью суффиксного массива

Пусть у нас есть образец [math] P [/math], строка [math] S [/math] и суффиксный массив [math] sufArray [/math]. Мы хотим найти все вхождения данного образца в данную строку. Существует несколько методов решения данной задачи.

Решение при помощи бинарного поиска

Понятно, что если образец [math] P [/math] входит в строку [math] S [/math], то он является префиксом какого-нибудь ее суффикса. Если вхождений несколько, то в суффиксном массиве [math] sufArray [/math] они будут находиться рядом друг с другом. Получается, что задача сводится к бинарному поиску в упорядоченном массиве.

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