Изменения

Пусть <tex> m_l = lcp(array[L], array[M]) </tex>, а <tex> m_r = lcp(array[M],array[R]) </tex>. Подсчет <tex> m_l </tex> и <tex> m_r </tex> можно производить за <tex> O(1) </tex>, если применять [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов <tex> array </tex> из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах. Аналогично любая пара суффиксов <tex> array </tex> из диапазона <tex> [M, R] </tex> имеет хотя бы <tex> m_r </tex> совпадений в префиксах. <br>

Рассмотрим поиск левой границы диапазона ответов <tex> L_p </tex>. <br>

<tex> L_p </tex> ищется при помощи бинарного поиска по суффиксному массиву <tex> array </tex>. На каждом шаге поиска нам надо определять, на каком отрезке <tex> [L, M] </tex> или <tex> [M, R] </tex> надо продолжать поиск границы <tex> L_p </tex>. Каждую итерацию бинарного поиска будем сравнивать <tex> m_l </tex> и <tex> m_r </tex>. Если <tex> m_l \ge m_r </tex>, то возможно одно из трех: <br>

* 1. <tex> m_l = l </tex>. Это означает, что у каждого суффикса из <tex> [L, M] </tex> есть хотя бы <tex> l </tex> совпадений с образцом. Проверим суффикс в позиции <tex> M </tex>, так как с ним совпадений у образца может получиться больше. Начнем сравнивать суффикс в позиции <tex> M </tex> начиная с <tex> l </tex>-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> R = M </tex> и <tex> r = |p| </tex>, так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ <tex> l + k </tex> у образца меньше, чем у суффикса, то <tex> R = M </tex> и <tex> m_r = l + k </tex>, иначе <tex> L = M </tex> и <tex> m_l = l + k </tex>.<br>