Изменения

1) <tex> m_l > l </tex>. Это означает, что каждый суффикс из диапазона <tex> [L, M] </tex> не подходит для <tex> L_p </tex>, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. <tex> l </tex> при этом не меняется, а <tex> L = M </tex>. <br>

2) <tex> m_l < l </tex>. Это означает, что совпадений у суффикса с левого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> M </tex>. Очевидно, что поиск надо продолжать между <tex> L </tex> и <tex> M </tex>, то есть <tex> R = M </tex>, а новое значение <tex> r = m_l </tex>. <br>

Осталось рассмотреть случай, когда <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>