Изменения
→Поиск границ диапазона ответов
Рассуждения при поиске <tex> R_p </tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>.
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex>\mathtt {lcp} </tex> между собой(каждое за <tex> O(1) </tex>), а если дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex>\mathtt {max}</tex><tex>(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l </tex> и <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex>\mathtt {lcp} </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>, начиная с позиции <tex> r </tex>.
===Псевдокод===
