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

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

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

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

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