Изменения

Пусть <tex> l = lcp(array[L], p) </tex>, а <tex> r = lcp(array[R], p) </tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </tex>. <br>

Пусть <tex> m_l = lcp(array[L], array[M]) </tex>, а <tex> r_l = lcp(array[M],array[R]) </tex>. Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|Алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах (Аналогично для диапазона <tex> [M, R] </tex>). <br>

Сразу проверим образец с краями исходного диапазона поиска. Если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе, и поиск можно прекратить. <br>

Границы диапазона ответов ищутся при помощи бинарного поиска. На каждом шаге поиска нам надо определять на каком отрезке (<tex> [L, M] </tex> или <tex> [M, L] </tex>) надо продолжать поиск <tex> L_p </tex>. Сравним <tex> m_l </tex> и <tex> m_r </tex>. Если <tex> m_l > m_r </tex>, то возможно одно из двух: <br>