Изменения
→Более быстрый поиск
Бинарный поиск будет работать до тех пор, пока <tex> R - L > 1 </tex>. После этого можно присвоить левой границе диапазона ответов <tex> L_p = R </tex> и переходить к поиску правой границы диапазона ответов <tex> R_p </tex>. <br>
Рассуждения при поиске <tex> R_p </tex> аналогичны, только нужно не забыть изменить границы поиска на изначальные <tex> L = 0 </tex> и <tex> R = |s| - 1 </tex>. <br>
Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex> lcp </tex> между собой (каждое за <tex> O(1) </tex>), а если уж и дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex> max(l, r) </tex>, а значит никогда не возвращаемся назад). В самом начале мы посчитали <tex> l </tex> и <tex> r </tex> за <tex> O(p) </tex>. В итоге получаем сложность алгоритма <tex> O(p + log(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex> lcp </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>.
==Литература==
* http://habrahabr.ru/blogs/algorithm/115346/
*U. Manber and G. Mayers. "Suffix arrays: A new method for on-line string searches"
