Изменения
Нет описания правки
так как <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> в суффиксном массиве предшествует
суффиксу <tex>i-1</tex>, то суффикс <tex>suf[suf^{-1}[{i-1}]-1] + 1</tex> будет предшествовать суффиксу <tex>i</tex> (но необязательно будет непоредственно непосредственно предыдущим), то <tex>height[suf^{-1}[i]] \ge lcp(i, suf[suf^{-1}[{i-1}]-1] + 1)</tex>, <tex>lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) - 1</tex>,
<tex>lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) = height[suf^{-1}[i-1]]</tex>, откуда <tex>height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1</tex>.
}}
