Рассмотрим такую задачу: у нас есть образец <tex> p </tex>, строка <tex> s </tex>, [[суффиксный массив|суффиксный массив]] <tex> array </tex>, построенный для строки <tex> s </tex>. Необходимо найти все вхождения образца <tex> p </tex> в строку <tex> s </tex>.{{В разработке}}
Для наглядности Здесь мы рассмотрим такой пример: образец '''''iss''''' , строка '''''mississippi''''' . <br>Вот некоторые способы нахождения всех вхождений образца в текст с помощью [[суффиксный массив для данной строки:|суффиксного массива]].
{| border="1" |width="20"|# |widthНаивный алгоритм поиска ="150"|суффикс |width="100"|номер суффикса Вспомним, что суффиксы в [[суффиксный массив|-суффиксном массиве]] расположены в лексикографическом порядке. Это позволяет нам |1 |искать с помощью двоичного поиска диапазон суффиксов в суффиксном массиве, первые <tex> i </tex> символов которых совпадают с первыми <tex> i |11 |- |2 |ippi |8 |- |3 |issippi |5 |- |4 |ississippi |2 |- |5 |mississippi |1 |- |6 |pi |10 |- |7 |ppi |9 |- |8 |sippi |7 |- |9 |sissippi |4 |- |10 |ssippi |6 |- |11 |ssissippi |3 |}</tex> символами образца.
== Способы поиска == === Простейший поиск подстроки ===...
Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по суффиксному массиву (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за время равное <tex> O(\log|s|) </tex>, а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы <tex> O(|p|\log|s|)</tex>. <br>
