== Наивный алгоритм поиска ==
Вспомним, что суффиксы в [[суффиксный массив|суффиксном массиве]] расположены в лексикографическом порядке. Это позволяет нам искать с помощью двоичного поиска диапазон суффиксов в суффиксном массиве, первые <tex> i </tex> символов которых совпадают с первыми <tex> i </tex> символами образца.
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по [[суффиксный массив|суффиксному массиву]] найти диапазон с суффиксами, начинающимися на такую же букву.Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы.А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца.
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по суффиксному массиву (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за время равное <tex> O(\log|s|) </tex>, а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы <tex> O(|p|\log|s|)</tex>. <br>
В примере поиск будет выглядеть так:
{| border="1" |width="80"|образец |width="150"|''Бинарный поиск работает за время равное <span style="color:#FF00FF"tex>i</span>ss'' O(\log|width="150"|''<span style="color:#FF00FF">is</span>s'' |width="150"|''<span style="color:#FF00FF">iss) </spantex>'', а сравнение суффикса с образцом не может превышать длины образца. |- | |''Таким образом время работы алгоритмы <span style="color:#FF00FF"tex>i</span>'' O(|i p|i \log|- s| |''<span style="color:#FF00FF">i</span>ppi'' |ippi |ippi |- | |''<span style="color:#FF00FF">i</span>ssippi'' |''<span style="color:#FF00FF">is</span>sippi'' |''<span style="color:#FF00FF">iss</span>ippi'' |- | |''<span style="color:#FF00FF">i</span>ssissippi'' |''<span style="color:#FF00FF">is</span>sissippi'' |''<span style="color:#FF00FF">iss</span>issippi'' |- | |mississippi |mississippi |mississippi |- | |pi |pi |pi |- | |ppi |ppi |ppi |- | |sippi |sippi |sippi |- | |sissippi |sissippi |sissippi |- | |ssippi |ssippi |ssippi |- | |ssissippi |ssissippi |ssissippi |}В примере показано, какие суффиксы на каждом шаге алгоритма удовлетворяют нашему образцу: на <tex> i </tex>-ом шаге суффикс является подходящим, если <tex> i </tex> его первых символов совпадают с <tex> i )</tex> первыми символами образца. Каждый шаг к рассмотрению добавляется лишь один новый символ образца. В графе "образец" розовым цветом выделен префикс образца, который ищется на данном шаге, а под образцом располагаются суффиксы строки, префиксы которых выделены розовым цветом, если на данном шаге суффикс подходит. <br>Как видно из примера образцу удовлетворяют суффиксы 3 и 4, начинающиеся на 5 и 2 позициях в строке соответственно(позицию можно посмотреть в таблице повыше).
=== Псевдокод ===
'''Поиск диапазона ''' /* p - образец n - длина образца left - левая граница диапазона // изначально равна единице
right - правая граница диапазона // изначально равна длине строки
lh - вспомогательная переменная для определения левой границы диапазона rg - вспомогательная переменная для определения правой границы диапазона find - функция уточнения диапазона элементы строк и массивов нумеруются с единицы */
for i = 1 to n {
lh = n + 1
right = rh
}
if (left != 0 && right != n + 1) { // если диапазон не пуст yield left // вывод левой границы диапазона yield right // вывод правой границы диапазона
} else
yield "No matches" // вывод информации об отсутствии вхождений
'''Бинарный поиск для уточнения диапазона ''' - функция find(l, r, k) /* l - левая граница диапазона при поиске r - правая граница диапазона при поиске k - номер символа образца, с которым происходит проверка на данном шаге s - строка
length - длина строки
array - суффиксный массив x - индекс, стоящий по середине между l и r */
if (l > r)
return
}
=== Более быстрый поиск ===
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>
