Изменения

Пусть при построении суффиксного массива для строки <tex> s </tex> был построен еще и массив <tex> LCP </tex>, <tex> i </tex>-ой позиции которого соответствует наибольший общий префикс <tex> i </tex>-ого и <tex> (i+1) </tex>-ого суффиксов. Все поиски <tex> lcp </tex> между парой парами суффиксов строки <tex> s </tex> производятся при помощи него. <br>Пусть <tex> L_p </tex> и <tex> R_p </tex> - левая и правая границы диапазона ответов. В пределах этого диапазона в суффиксном массиве <tex> array </tex> лежат суффиксы, префиксы которых полностью совпадают с образцом <tex> p </tex>. Пусть <tex> L </tex> - левая граница текущего диапазона поиска (изначально равна 0), <tex> R_p R </tex> - правая граница текущего диапазона поиска (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex> . <br>

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