Изменения

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

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

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

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