275
правок
Изменения
м
→Описание алгоритма и псевдокод
'''int[]''' buildLCP(str: '''string''', suf: '''int[]''') <font color=green> // str {{---}} исходная строка с добавленным специальным символом $ </font>
<font color=green> // suf[] {{---}} суффиксный массив строки str </font>
'''int''' len <tex>\leftarrow=</tex> str.length
'''int[len]''' lcp
'''int[len]''' pos <font color=green> // pos[] {{---}} массив, обратный массиву suf </font>
'''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''' max(i + k, j + k) < len '''and''' str[i + k] == str[j + k]
k++
lcp[pos[i]] <tex>\leftarrow=</tex> k
'''return''' lcp
