Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <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>.
===Разбор случаев=== Условные обозначения: Ищется левая граница ответов <tex> L_p </tex>. Разберем случай <tex> l \ge r </tex>. Возможны три варианта: [[Файл:left.png]] * a) <tex> l < m_l </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>. Значение <tex> l </tex> не изменяется.* b) <tex> l = m_l </tex>. Считаем <tex> lcp </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>, начиная с позиции <tex> l </tex>.* с) <tex> l > m_l </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>, <tex> r = m_l </tex>. Разберем случай при <tex> l < r </tex>. Также возможны три варианта: [[Файл:right2.png]] * a) <tex> r < m_r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.* b) <tex> r = m_r </tex>. Считаем <tex> lcp </tex> для образца и суффикса, стоящего в позиции <tex> M </tex>, начиная с позиции <tex> r </tex>.
* с) <tex> r > m_r </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>, <tex> l = m_r </tex>.
