Изменения

Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов. В У любого суффикса в пределах этого диапазона в суффиксном массиве <tex> array </tex> лежат суффиксыесть префикс, префиксы которых который полностью совпадают совпадает с образцом <tex> p </tex>.

Пусть <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>, если применять [[Алгоритм Фарака-Колтона и Бендера|Алгоритм fлгоритм Фарака-Колтона и Бендера]]. Любая пара суффиксов из диапазона <tex> [L, M] </tex> имеет хотя бы <tex> m_l </tex> совпадений в префиксах (. Аналогично для диапазона <tex> [M, R] </tex>)и <tex> m_r </tex>. <br>Рассмотрим поиск левой границы диапазона ответов <tex> L_p </tex>(поиск правой границы <tex> R_p </tex> производится аналогично). <br>Сразу проверим образец с краями суффиксами по краям исходного диапазона поиска<tex> L </tex> и <tex> R </tex>. Если образец лексикографически больше последнего суффикса <tex> array </tex> или меньше первого суффикса, то образец не встречается в строке вовсе, и поиск можно прекратить. <br>Границы диапазона ответов ищутся <tex> L_p </tex> ищется при помощи бинарного поиска. На каждом шаге поиска нам надо определять, на каком отрезке (<tex> [L, M] </tex> или <tex> [M, LR] </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 </tex> совпадений с образцом. А значит можно сравнивать суффикс в позиции <tex> M </tex> начиная с <tex> l </tex>-ого символа. Мы либо найдем полное вхождение образца в суффикс, либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> R = M </tex> и <tex> r = |p| </tex>. Во втором случае все зависит от лексикографического несовпадения. <br>2) <tex> m_l > l </tex>. Это означает, что каждая пара суффиксов из диапазона <tex> L_p [L, M] </tex>имеет между собой больше совпадений, чем суффикс с левого края с образцом, поэтому продолжим поиск в диапазоне <tex> [M, R] </tex>. <tex> l </tex> при этом не меняется, а <tex> L = M </tex>. <br>23) <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 [M, R] </tex> и есть хотя бы <tex> r </tex>, и во втором случае меняется совпадений с образцом. А значит можно сравнивать суффикс в позиции <tex> L M </tex> и начиная с <tex> l r </tex>-ого символа.Осталось рассмотреть случайМы либо найдем полное вхождение образца в суффикс, когда либо на каком-то шаге <tex> k </tex> получим несоответствие. В первом случае <tex> m_l R = l M </tex> и <tex> r = |p| </tex>. Во втором случае все зависит от лексикографического несовпадения. <br>2) <tex> m_r = > r </tex>. Если хоть одно равенство не выполняетсяЭто означает, то результат известен что каждая пара суффиксов из предыдущего абзаца. Тогда яснодиапазона <tex> [M, что R] </tex> lcp(pимеет между собой больше совпадений, чем суффикс с правого края с образцом, arrayпоэтому продолжим поиск в диапазоне <tex> [L, M]) </tex> никак . <tex> r </tex> при этом не меньше меняется, а <tex> R = M </tex>. <br>3) <tex> max(l, m_r < r) </tex>. А значит можно сравнивать символы Это означает, что совпадений у суффикса с правого края диапазона поиска с образцом больше, чем у суффикса в позиции <tex> array[M] </tex>. Очевидно, что поиск надо продолжать между <tex> M </tex> и образца начиная с <tex> max(R </tex>, то есть <tex> L = M </tex>, а новое значение <tex> l, r) = m_r </tex> позиции.<br> При сравнении мы либо полностью найдем вхождение образца в суффиксБинарный поиск будет работать до тех пор, либо на каком-то шаге пока <tex> k R - L > 1 </tex> наткнемся на различие . В первом случае нам надо определять дальнейшее место поиска исходя из того, что мы ищем После этого можно присвоить левой границе диапазона ответов <tex> L_p = R </tex> или и переходить к поиску правой границы <tex> R_p </tex> (мы искали . <br>Рассуждения при поиске <tex> L_p R_p </tex>, поэтому только нужно не забыть изменить границы поиска на изначальные <tex> r L = max(l, r) + k 0 </tex>, и <tex> R = M |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>.