Изменения
Нет описания правки
}}
Таким образом, начиная проверять <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>.
