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

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

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

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