Изменения
Нет описания правки
| <tex>\bot</tex> || <tex>0</tex> || <tex>1</tex> || <tex>2</tex> || <tex>1</tex> || <tex>1</tex> || <tex>0</tex> || <tex>0</tex>
|}
Например <tex>\mathrm{Height}[3] = 2</tex> {{---}} это длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</tex>.
===Вспомогательные утверждения===
Теперь рассмотрим следующую задачу: рассчитать <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>.
{{Лемма|statement=
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>.
|proof=
Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из факта №2. Так как <tex>Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> из факта №1
Если <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>
|proof=
<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (из леммы).
<tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта №3).
Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex> .
}}
