Изменения
Нет описания правки
'''Алгоритм Касаи''' (Аримуры-Арикавы-Касаи-Ли-Парка) {{--- }} алгоритм, позволяющий за линейное время вычислить
значения наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом
порядке (largest common prefix, далее <tex>lcp</tex>).
==Обозначения==
<tex>S - </tex> {{---}} данная строка.
<tex>height[i] - </tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>suf[i]</tex> и <tex>suf[i-1]</tex> соответственно).
<tex>suf^{-1}</tex> {{- --}} обратный суффиксный массив, удовлетворяющий свойству <tex>suf^{-1}[suf[i]] = i</tex>.
Может быть построен одним линейным проходом по суффиксному массиву.
