Изменения

|proof=

<tex>height[suf^{-1}[i-1]] = lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]})</tex>, <tex>height[suf^{-1}[i]] = lcp(S_{i}, S_{suf[suf^{-1}[{i}]-1]})</tex>.

так как <tex>i-1</tex> и <tex>i</tex> суффикс отличаются только первым символом, как и <tex>suf[suf^{-1}[{i-1}]-1]</tex> с <tex>suf[suf^{-1}[{i-1}]-1] + 1</tex>, то

<tex>lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(i-1, suf[suf^{-1}[{i-1}]-1]) - 1</tex>. Так как суффикс <tex>suf[suf^{-1}[{i-1}]-1]</tex> в суффиксном массиве предшествует