Алгоритм Касаи и др.

Алгоритм Касаи (Аримуры-Арикавы-Касаи-Ли-Парка) --- алгоритм, позволяющий за линейное время вычислить значения наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом порядке(largest common prefix, далее lcp).