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

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

Обозначения

[math]S[/math] — данная строка.

[math]height[i][/math] — длина наибольшего общего префикса [math]i[/math] и [math]i-1[/math] строк в суффиксном массиве ([math]suf[i][/math] и [math]suf[i-1][/math] соответственно).

[math]suf^{-1}[/math] — обратный суффиксный массив, удовлетворяющий свойству [math]suf^{-1}[suf[i]] = i[/math]. Может быть построен одним линейным проходом по суффиксному массиву.

Все массивы и строка имеют 0-индексацию.

Описание алгоритма

Значения [math]height[/math] считаются для все суффиксов строки последовательно. Значение [math]height[suf^{-1}[0]][/math] считается наивным методом за линейное время. Покажем, как вычислить [math]height[suf^{-1}[i]][/math], если значение [math]height[suf^{-1}[i-1]][/math] известно.

Теорема:

Если [math]height[suf^{-1}[i-1]] \gt 0[/math], то [math]height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1[/math].

Доказательство:

[math]\triangleright[/math]

[math]height[suf^{-1}[i-1]] = lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]})[/math], [math]height[suf^{-1}[i]] = lcp(S_{i}, S_{suf[suf^{-1}[{i}]-1]})[/math]. Рассмотрим суффиксный массив и позиции в нем суффиксов [math]i, i-1, suf[suf^{-1}[{i-1}]-1][/math]: так как [math]i-1[/math] и [math]i[/math] суффикс отличаются только первым символом, как и [math]suf[suf^{-1}[{i-1}]-1][/math] с [math]suf[suf^{-1}[{i-1}]-1] + 1[/math], то [math]lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(i-1, suf[suf^{-1}[{i-1}]-1]) - 1[/math]. Так как суффикс [math]suf[suf^{-1}[{i-1}]-1][/math] в суффиксном массиве предшествует суффиксу [math]i-1[/math], то суффикс [math]suf[suf^{-1}[{i-1}]-1] + 1[/math] будет предшествовать суффиксу [math]i[/math] (но необязательно будет непосредственно предыдущим), то [math]height[suf^{-1}[i]] \ge lcp(i, suf[suf^{-1}[{i-1}]-1] + 1)[/math], [math]lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) - 1[/math], [math]lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) = height[suf^{-1}[i-1]][/math], откуда [math]height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1[/math].

[math]\triangleleft[/math]

Таким образом, начиная проверять [math]lcp[/math] для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить [math]lcp[/math]. Покажем, что построение [math]lcp[/math] таким образом действительно требует [math]O(N)[/math] времени. Действительно, на каждой итерации текущее значение [math]lcp[/math] может быть не более чем на единицу меньше предыдущего. Таким образом, значения [math]lcp[/math] в сумме могут увеличиться не более, чем на 2N (с точностью до константы). Следовательно, алгоритм построит [math]lcp[/math] за [math]O(N)[/math].

Источники

1. Алгоритм Касаи.
2. T.Kasai, G.Lee, H.Arimura, S.Arikawa, K.Park - Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application.