Изменения

значения длину наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом

Задана строка <tex>AS</tex>. Тогда <tex>A_S_{i}</tex> {{---}} суффикс строки <tex>AS</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив <tex>PosSuf</tex>. Для вычисления <tex>LCP</tex> будем использовать промежуточный массив <tex>RankSuf^{-1}</tex>. Массив <tex>RankSuf^{-1}</tex> определен как обратный к массиву <tex>PosSuf</tex>. Он может быть получен немедленно, если задан массив <tex>PosSuf</tex>. Если <tex>PosSuf[k] = i</tex>, то <tex>RankSuf^{-1}[i] = k</tex>.

<tex>Height[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>PosSuf[i]</tex> и <tex>PosSuf[i-1]</tex> соответственно).

<tex>LCP</tex> между двумя суффиксами {{---}} это минимум <tex>LCP</tex> всех пар смежных соседних суффиксов между ними в суффиксном массиве <tex>PosSuf</tex>. То есть <tex>LCP(A_S_{PosSuf[x]}, A_S_{PosSuf[z]}) = min_{x < y \le z}(LCP(A_S_{PosSuf[y - 1]},A_S_{PosSuf[y]})</tex>.Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>PosSuf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.

|statement=<tex>LCP(A_S_{PosSuf[y - 1]}, A_S_{PosSuf[y]}) \le LCP(A_S_{PosSuf[x]},A_S_{PosSuf[z]}), x < y \le z</tex>

Если значение <tex>LCP</tex> между парой соседних суффиксов, смежных соседних в массиве <tex>PosSuf</tex> больше <tex>1</tex>, то лексикографический порядок суффиксов сохранится, если и можно удалить первый символ каждого суффикса.<br>

Если <tex>LCP(A_S_{PosSuf[x-1]} , A_S_{PosSuf[x]} ) > 1</tex>, тогда <tex>RankSuf^{-1}[PosSuf[x - 1] + 1] < RankSuf^{-1}[PosSuf[x] + 1]</tex>

В этом же случае, значение <tex>LCP</tex> между <tex>A_S_{PosSuf[x-1]+1}</tex> и <tex>A_S_{PosSuf[x]+1}</tex> на один меньше значения <tex>LCP</tex> между <tex>A_S_{PosSuf[x-1]}</tex> и <tex>A_S_{PosSuf[x]}</tex>.<br>

|statement=Если <tex>LCP(A_S_{PosSuf[x-1]} , A_S_{PosSuf[x]} ) > 1</tex>, тогда <tex>LCP(A_S_{PosSuf[x-1]+1} , A_S_{PosSuf[x]+1}) = LCP(A_S_{PosSuf[x-1]} , A_S_{PosSuf[x]} ) - 1</tex>

===Вспомогательные утверждения=== Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>A_S_{i}</tex> и его смежным соседних суффиксом в массиве <tex>PosSuf</tex>, при условии, что значение <tex>LCP</tex> между <tex>A_S_{i-1}</tex> и его смежным соседним суффиксом известны. Для удобства записи пусть <tex>p=RankSuf^{-1}[i - 1]</tex> и <tex>q = RankSuf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = PosSuf[p-1]</tex> и <tex>k = PosSuf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>Height[q]</tex>, когда задано <tex>Height[p]</tex>

Если <tex>LCP(A_S_{j-1}, A_S_{i-1}) > 1</tex>, тогда <tex>LCP(A_kS_k,A_iS_i) \le LCP(A_jS_j,A_iS_i)</tex>

Так как <tex>LCP(A_S_{j−1},A_S_{i−1}) > 1</tex>, имеем <tex>RankSuf^{-1}[j] < RankSuf^{-1}[i]</tex> из факта №2. Так как <tex>RankSuf^{-1}[j] \le RankSuf^{-1}[k] = RankSuf^{-1}[i] - 1</tex>, имеем <tex>LCP(A_S_{k} , A_S_{i}) \ge LCP(A_S_{j} , A_S_{i})</tex> из факта №1

Если <tex>Height[p] = lcpLCP(A_S_{j-1}, A_S_{i-1}) > 1</tex>, то <tex>Height[q] = lcpLCP(A_S_{k}, A_S_{i}) \ge Height[p] - 1</tex>

<tex>LCP(A_S_{k}, A_S_{i}) \ge LCP(A_S_{j} , A_S_{i})</tex>(из Леммы) = <tex>LCP(A_S_{j-1}, A_S_{i−1}) - 1</tex> (из факта №3).

Таким образом, начиная проверять <tex>lcpLCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>lcpLCP</tex>.Покажем, что построение <tex>lcpLCP</tex> таким образом действительно требует <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>lcpLCP</tex> может быть не болеечем на единицу меньше предыдущего. Таким образом, значения <tex>lcpLCP</tex> в сумме могут увеличиться не более, чем на <tex>2N</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>lcpLCP</tex> за <tex>O(N)</tex>.