Изменения
→Условные обозначения
Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex>\mathtt {lcp} </tex> (longest common prefix).
* <tex> L_p </tex> и <tex> R_p </tex> {{---}} левая и правая границы диапазона ответов в суффиксном массиве <tex> array </tex>.
* <tex> L </tex> {{---}} левая граница диапазона поиска (изначально равна <tex>0</tex>).
* <tex> R </tex> {{---}} правая граница диапазона поиска (изначально равна <tex> |S| - 1 </tex>).
* <tex> M = (L + R) / 2 </tex>.
* <tex> l = </tex><tex>\mathtt {lcp(array[L], p)} </tex>.
* <tex> r = </tex><tex>\mathtt {lcp(array[R], p)} </tex>.
* <tex> m_l = </tex><tex>\mathtt {lcp(array[L], array[M])} </tex>.
* <tex> m_r = </tex><tex>\mathtt {lcp(array[M], array[R])} </tex>.
У любого суффикса в пределах диапазона от <tex> L_p </tex> до <tex> R_p </tex> есть префикс, который полностью совпадает с образцом.
В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>.
Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов <tex> array </tex> из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах. Аналогично любая пара суффиксов <tex> array </tex> из диапазона <tex> [M, R] </tex> имеет хотя бы <tex> m_r </tex> совпадений в префиксах.
