322
правки
Изменения
→Описание алгоритма
==Описание алгоритма==
Значения <tex>height</tex> считаются для все всех суффиксов строки последовательно. Значение <tex>height[suf^{-1}[0]]</tex> считается
наивным методом за линейное время. Покажем, как вычислить <tex>height[suf^{-1}[i]]</tex>, если значение <tex>height[suf^{-1}[i-1]]</tex>
известно.
Таким образом, начиная проверять <tex>lcp</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>lcp</tex>.
Покажем, что построение <tex>lcp</tex> таким образом действительно требует <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>lcp</tex> может быть не более
чем на единицу меньше предыдущего. Таким образом, значения <tex>lcp</tex> в сумме могут увеличиться не более, чем на <tex>2N </tex> (с точностью до константы). Следовательно, алгоритм построит <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].
