Изменения

Существует более быстрый алгоритм поиска образца в строке. Для этого используется <tex> lcp </tex> (longest common prefix). <br>Пусть при построении суффиксного массива для строки <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> - левая граница текущего диапазона (изначально равна 0), а <tex> R_p </tex> - правая граница текущего диапазона (изначально равна <tex> |S| - 1 </tex>), а <tex> M = (L + R) / 2 </tex> <br>Пусть <tex> l = lcp(array[L], p) </tex>, а <tex> r = lcp(array[R], p) </tex>. В самом начале просто посчитаем <tex> l </tex> и <tex> r </tex> за линейное время, а во время выполнения алгоритма прямой пересчет производиться не будет, изменения будут происходить за <tex> O(1) </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>, если применять [[Алгоритм Фарака-Колтона и Бендера|Алгоритм Фарака-Колтона и Бендера]].