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

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

Обозначения

Задана строка [math]A[/math]. Тогда [math]A_{i}[/math] — суфикс строки [math]A[/math], начинающийся в [math]i[/math]-ом символе. Пусть задан суфиксный массив [math]Pos[/math]. Для вычисления [math]LCP[/math] будем использовать промежуточный массив [math]Rank[/math]. Массив [math]Rank[/math] определен как обратный к массиву [math]Pos[/math]. Он может быть получен немедленно, если задан массив [math]Pos[/math]. Если [math]Pos[k] = i[/math], то [math]Rank[i] = k[/math].

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

Некоторые свойства [math]LCP[/math]

Факт №1

[math]LCP[/math] между двумя суфиксами — это минимум [math]LCP[/math] всех пар смежных суфиксов между ними в суфиксном массиве [math]Pos[/math]. То есть [math]LCP(A_{Pos[x]}, A_{Pos[z]}) = min_{x \lt y \le z}(LCP(A_{Pos[y - 1]},A_{Pos[y]})[/math]. Отсюда следует, что [math]LCP[/math] пары соседних суфиксов в массиве [math]Pos[/math] больше или равно [math]LCP[/math] пары суфиксов, окружающих их.

Утверждение:

[math]LCP(A_{Pos[y - 1]}, A_{Pos[y]}) \le LCP(A_{Pos[x]},A_{Pos[z]}), x \lt y \le z[/math]

Факт №2

Если значение [math]LCP[/math] между парой соседних суфиксов, смежных в массиве [math]Pos[/math] больше [math]1[/math], то лексикографический порядок суффиксов сохранится, если удалить первый символ каждого суффикса.

Утверждение:

Если [math]LCP(A_{Pos[x-1]} , A_{Pos[x]} ) \gt 1[/math], тогда [math]Rank[Pos[x - 1] + 1] \lt Rank[Pos[x] + 1][/math]

Факт №3

В этом же случае, значение [math]LCP[/math] между [math]A_{Pos[x-1]+1}[/math] и [math]A_{Pos[x]+1}[/math] на один меньше значения [math]LCP[/math] между [math]A_{Pos[x-1]}[/math] и [math]A_{Pos[x]}[/math].

Утверждение:

Если [math]LCP(A_{Pos[x-1]} , A_{Pos[x]} ) \gt 1[/math], тогда [math]LCP(A_{Pos[x-1]+1} , A_{Pos[x]+1}) = LCP(A_{Pos[x-1]} , A_{Pos[x]} ) - 1[/math]

Теперь рассмотрим следующую задачу: расчитать [math]LCP[/math] между суфиксом [math]A_{i}[/math] и его смежным суфиксом в массиве [math]Pos[/math], при условии, что значение [math]LCP[/math] между [math]A_{i-1}[/math] и его смежным суфиксом известны. Для удобства записи пусть [math]p=Rank[i - 1][/math] и [math]q = Rank[i][/math]. Так же пусть [math]j - 1 = Pos[p-1][/math] и [math]k = Pos[q - 1][/math]. Проще говоря, мы хотим посчитать [math]Height[q][/math], когда задано [math]Height[p][/math]

Лемма:

Если [math]LCP(A_{j-1}, A_{i-1}) \gt 1[/math], тогда [math]LCP(A_k,A_i) \le LCP(A_j,A_i)[/math]

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

[math]\triangleright[/math]

Так как [math]LCP(A_{j−1},A_{i−1}) \gt 1[/math], имеем [math]Rank[j] \lt Rank[i][/math] из факта №2. Так как [math]Rank[j] \le Rank[k] = Rank[i] - 1[/math], имеем [math]LCP(A_{k} , A_{i}) \ge LCP(A_{j} , A_{i})[/math] из факта №1

[math]\triangleleft[/math]

Теорема:

Если [math]Height[p] = lcp(A_{j-1}, A_{i-1}) \gt 1[/math], то [math]Height[q] = lcp(A_{k}, A_{i}) \ge Height[p] - 1[/math]

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

[math]\triangleright[/math]

[math]LCP(A_{k}, A_{i}) \ge LCP(A_{j} , A_{i})[/math](из Леммы) = [math]LCP(A_{j-1}, A_{i−1}) - 1[/math] (из факта №3).

[math]\triangleleft[/math]

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

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