Изменения
→Более быстрый поиск
Рассмотрим поиск левой границы диапазона ответов <tex> L_p </tex>(поиск правой границы <tex> R_p </tex> производится аналогично). <br>
Сразу проверим образец с краями исходного диапазона поиска. Если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе, и поиск можно прекратить. <br>
Границы диапазона ответов ищутся при помощи бинарного поиска. На каждом шаге поиска нам надо определять, на каком отрезке (<tex> [L, M] </tex> или <tex> [M, L] </tex>) надо продолжать поиск границы <tex> L_p </tex>. Сравним Каждую итерацию бинарного поиска будем сравнивать <tex> m_l </tex> и <tex> m_r </tex>. Если <tex> m_l > m_r </tex>, то возможно одно из двух: <br>
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>
