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

2012-05-03T19:51:09Z

178.178.27.113: /* Факт №2 */

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

==Обозначения==
Задана строка <tex>S</tex>. Тогда <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив <tex>Suf</tex>. Для вычисления <tex>LCP</tex> будем использовать промежуточный массив <tex>Suf^{-1}</tex>. Массив <tex>Suf^{-1}</tex> определен как обратный к массиву <tex>Suf</tex>. Он может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.

<tex>Height[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).

==Некоторые свойства <tex>LCP</tex>==
===Факт №1===
<tex>LCP</tex> между двумя суффиксами {{---}} это минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min_{x < y \le z}(LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.
Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.

{{Утверждение
|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \ge LCP(S_{Suf[x]},S_{Suf[z]}), x < y \le z</tex>
}}

===Факт №2===
Если значение <tex>LCP</tex> между парой суффиксов, соседних в массиве <tex>Suf</tex>, больше <tex>1</tex>, то можно удалить первый символ каждого суффикса и лексикографический порядок суффиксов сохранится.<br>
{{Утверждение
|statement=
Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 1]</tex>
}}

===Факт №3===
В этом же случае, значение <tex>LCP</tex> между <tex>S_{Suf[x-1]+1}</tex> и <tex>S_{Suf[x]+1}</tex> на один меньше значения <tex>LCP</tex> между <tex>S_{Suf[x-1]}</tex> и <tex>S_{Suf[x]}</tex>.<br>
{{Утверждение
|statement=Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>LCP(S_{Suf[x-1]+1} , S_{Suf[x]+1}) = LCP(S_{Suf[x-1]} , S_{Suf[x]} ) - 1</tex>
}}

===Вспомогательные утверждения===

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

{{Лемма|statement=
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \ge LCP(S_j,S_i)</tex>
|proof=
Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из факта №2. Так как <tex>Suf^{-1}[j] \le Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \ge LCP(S_{j} , S_{i})</tex> из факта №1
}}

{{Теорема|statement=
Если <tex>Height[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>Height[q] = LCP(S_{k}, S_{i}) \ge Height[p] - 1</tex>
|proof=
<tex>LCP(S_{k}, S_{i}) \ge LCP(S_{j} , S_{i})</tex>(из Леммы) = <tex>LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта №3).
}}

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

==Источники==
1. [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B0%D1%81%D0%B0%D0%B8 Алгоритм Касаи].<br/>
2. [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.8221 T.Kasai, G.Lee, H.Arimura, S.Arikawa, K.Park - Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application].

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Суффиксный массив]]

Викиконспекты - Вклад участника [ru]

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