Изменения
→Более быстрый поиск
3) <tex> m_r < r </tex>. Это означает, что совпадений у суффикса с правого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> M </tex> и <tex> R </tex>, то есть <tex> L = M </tex>, а новое значение <tex> l = m_r </tex>. <br>
Бинарный поиск будет работать до тех пор, пока <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(plogp + 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"
