Изменения

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

Если <tex>\mathrm{Height}[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>\mathrm{Height}[q] = LCP(S_{k}, S_{i}) \geqslant \mathrm{Height}[p] - 1</tex>