Алгоритм Касаи (Аримуры-Арикавы-Касаи-Ли-Парка) --- алгоритм, позволяющий за линейное время вычислить
значения наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом
порядке (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}[1]][/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] |
