Изменения
→Более быстрый поиск
<tex> L_p </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>
2) <tex> m_l > l </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [L, M] </tex> имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. Значение <tex> l </tex> при этом не меняется, а <tex> L = M </tex>. <br>
3) <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 < m_r </tex>, то действия аналогичны: <br>
1) <tex> m_r = r </tex>. Это означает, что у каждого суффикса из <tex> [M, R] </tex> есть хотя бы <tex> r </tex> совпадений с образцом. Проверим суффикс в позиции <tex> M </tex>, так как с ним совпадений у образца может получиться больше. Можно сравнивать суффикс в позиции <tex> M </tex> начиная с <tex> r </tex>-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> R = M </tex> и <tex> r = |p| </tex>, так как мы ищем левую границу диапазона ответов. Во втором случае все зависит от лексикографического несовпадения. Если символ <tex> r + k </tex> у образца меньше, чем у суффикса, то <tex> R = M </tex> и <tex> m_r = r + k </tex>, иначе <tex> L = M </tex> и <tex> m_l = r + k </tex>. <br>
2) <tex> m_r > r </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> [M, R] </tex> имеет между собой больше совпадений, чем суффикс с правого края с образцом, поэтому продолжим поиск в диапазоне <tex> [L, M] </tex>. Значение <tex> r </tex> при этом не меняется, а <tex> R = M </tex>. <br>
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> p </tex> сравнивается не более одного раза(при сравнении мы берем <tex> max(l, r) </tex>, а значит никогда не возвращаемся назад). Получаем сложность алгоритма <tex> O(plog(s)) </tex>. Правда нужен предподсчет, чтобы можно было брать <tex> lcp </tex> для двух любых суффиксов <tex> array </tex> за <tex> O(1) </tex>.
