Изменения

Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и бинарным поиском по суффиксному массиву (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в полученном диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска уже по второму, затем третьему и так до конца далее символу образца до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Бинарный поиск работает за <tex> O(log|s|) </tex>, а сравнение суффикса с образцом не может превышать длины образца. Таким образом время работы алгоритмы <tex> O(|p|log|s|)</tex>.<br>В примере поиск будет выглядеть так: {| border="1" |width="80"|образец |width="150"|'''''i'''ss'' |width="150"|'''''is'''s'' |width="150"|'''''iss''''' |- | |i |i |i |- | |ippi |ippi |ippi |- | |issippi |issippi |issippi |- | |ississippi |ississippi |ississippi |- | |mississippi |mississippi |mississippi |- | |pi |pi |pi |- | |ppi |ppi |ppi |- | |sippi |sippi |sippi |- | |sissippi |sissippi |sissippi |- | |ssippi |ssippi |ssippi |- | |ssissippi |ssissippi |ssissippi |}