137
правок
Изменения
→Описание алгоритма
}}
==Описание алгоритмаи псевдокод==
Таким образом, начиная проверять <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>.
'''int[]''' build_lcp(str : '''string''', suf : '''int[]''') // str {{---}} исходная строка с добавленным специальным символом $
// suf[] {{---}} суффиксный массив строки str
'''int''' len <tex>\leftarrow</tex> str.length
'''int[len]''' lcp
'''int[len]''' pos // pos[] {{---}} массив, обратный массиву suf
'''for''' i = 0 '''to''' len - 1
pos[suf[i]] <tex>\leftarrow</tex> i
'''int''' k <tex>\leftarrow</tex> 0
'''for''' i = 0 '''to''' len - 1
'''if''' k > 0
k--
'''if''' pos[i] == len - 1
lcp[len - 1] <tex>\leftarrow</tex> -1
k <tex>\leftarrow</tex> 0
'''else'''
'''int''' j <tex>\leftarrow</tex> suf[pos[i] + 1]
'''while''' str[i + k] == str[j + k]
k++
lcp[pos[i]] <tex>\leftarrow</tex> k;
'''return''' lcp
==Источники информации==
