Изменения
→Более быстрый поиск
Если <tex> m_l < m_r </tex>, то действия аналогичны, только сравнения надо проводить с <tex> m_r </tex>, и во втором случае меняется <tex> L </tex> и <tex> l </tex>.
Осталось рассмотреть случай, когда <tex> m_l = l </tex> и <tex> m_r = r </tex>. Если хоть одно равенство не выполняется, то результат известен из предыдущего абзаца. Тогда ясно, что <tex> lcp(p, array[M]) </tex> никак не меньше <tex> max(l, r) </tex>. А значит можно сравнивать символы суффикса в позиции <tex> array[M] </tex> и образца начиная с <tex> max(l, r) </tex> позиции.
При сравнении мы либо полностью найдем вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> наткнемся на различие . В первом случае нам надо определять дальнейшее место поиска исходя из того, что мы ищем <tex> L_p </tex> или <tex> R_p </tex> (мы искали <tex> L_p </tex>, поэтому <tex> r = max(l, r) + k </tex>, <tex> R = M </tex>). Во втором случае все определяется лексикографически. <br>Таким образом часть бинарного поиска мы сделаем при сравнении нескольких <tex> lcp </tex> между собой, а если уж и дойдет до сравнения символов, то любой символ <tex> p </tex> сравнивается не более одного раза(мы берем <tex> max(l, r) </tex>, а значит никогда не возвращаемся назад). Получаем сложность алгоритма <tex> O(plog(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex> lcp </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>.
==Литература==
* http://habrahabr.ru/blogs/algorithm/115346/
