Изменения
Нет описания правки
Таким образом, начиная проверять <tex>lcp</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>lcp</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].
