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

Пусть у нас есть образец [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].

Улучшение бинарного поиска

При двоичном поиске обозначим левую и правую границы текущего интервала как [math] L [/math] и [math] R [/math] соответственно. Изначально [math] L = 0 [/math], [math] R = |S| - 1 [/math]. На каждой итерации будем сравнивать образец [math] P [/math] с суффиксом [math] sufArray[(L + R) / 2] [/math]. Обозначим за [math] left [/math] длину общего префикса [math] P [/math] и [math] sufArray[L] [/math], а за [math] right [/math] длину общего префикса [math] P [/math] и [math] sufArray[R] [/math]. Также обозначим за [math] minRange [/math] минимум из [math] left [/math] и [math] right [/math]. Значение [math] minRange [/math] будем поддерживать на каждой итерации двоичного поиска. Теперь, зная [math] minRange [/math], можно начинать сравнение образца [math] P [/math] с суффиксом [math] sufArray[(L + R) / 2] [/math], начиная с [math] minRange + 1 [/math] символа. Это возможно, так как для любого суффикса из нашей границы от [math] L [/math] до [math] R [/math] первые [math] minRange [/math] символов совпадают. Если бы это было не так, то в суффиксном массиве в границе от [math] L [/math] до [math] R [/math] были бы суффиксы, которые сначала имеют [math] minRange [/math] совпадений, затем не имеют, а затем снова имеют, что говорит о неправильном построении суффиксного массива.
При таком поиске время работы равно [math] O(|P| + log|S|) [/math].