Изменения
Нет описания правки
<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>.
}}
Покажем, что построение <tex>lcp</tex> таким образом займет <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>lcp</tex> может быть не более
чем на единицу меньше предыдущего. Таким образом, значения <tex>lcp</tex> в сумме могут увеличиться не более, чем на 2N (с точностью до константы). Следовательно, алгоритм построит массив <tex>lcp</tex> за <tex>O(N)</tex>.
==Источники==
1. [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%81%D0%B0%D0%B8 Алгоритм Касаи].<br/>
2. [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.8221 T.Kasai, G.Lee, H.Arimura, S.Arikawa, K.Park - Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application].
