Изменения

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

Задана строка Введём следующие обозначения:* <tex>AS</tex>{{---}} данная строка. Тогда * <tex>A_S_{i}</tex> {{---}} суффикс строки <tex>AS</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив * <tex>PosSuf</tex>{{---}} [[Суффиксный массив | суффиксный массив]]. Для вычисления * <tex>LCPSuf^{-1}</tex> будем использовать промежуточный {{---}} массив <tex>Rank</tex>. Массив <tex>Rank</tex> определен как , обратный к массиву <tex>Pos</tex>. Он суффиксному, который может быть получен немедленно, если задан массив <tex>PosSuf</tex>. Если <tex>PosSuf[k] = i</tex>, то <tex>RankSuf^{-1}[i] = k</tex>.  * <tex>HeightLCP(S_{Suf[x]}, S_{Suf[iz]})</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>PosS_{Suf[ix]}</tex> и <tex>PosS_{Suf[i-1z]}</tex> соответственно). ==Некоторые свойства * <tex>LCP</tex>=====Факт №1===<tex>LCPlcp[i]</tex> между двумя суффиксами {{---}} это минимум длина наибольшего общего префикса соседних строк <tex>LCPi-1</tex> всех пар смежных суффиксов между ними в суффиксном массиве и <tex>Posi</tex>. То , то есть <tex>LCP(A_{Poslcp[x]}, A_{Pos[zi]}) = min_{x < y \le z}(LCP(A_S_{PosSuf[y i- 1]},A_S_{PosSuf[yi]})</tex>.Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Pos</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.

|id = fact1|about= №1|statement=<tex>LCP(A_S_{PosSuf[y - 1]}, A_S_{PosSuf[y]}) \le geqslant LCP(A_S_{PosSuf[x]},A_S_{PosSuf[z]}), x < y \le leqslant z</tex>|proof=<tex>LCP</tex> между двумя суффиксами {{---}} минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{x < y \leqslant z}LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.

 ===Факт №2===Если значение Также заметим, что <tex>LCP</tex> между парой соседних суффиксов(S_{Suf[x]}, смежных в массиве <tex>Pos</tex> больше <tex>S_{Suf[z]}) = \min\limits_{i = x + 1\ldots z}lcp[i]</tex>, то лексикографический порядок суффиксов сохранится, если удалить первый символ каждого суффикса.<br>

Если <tex>LCP(A_S_{PosSuf[x-1]} , A_S_{PosSuf[x]} ) > 1</tex>, тогда <tex>RankSuf^{-1}[PosSuf[x - 1] + 1] < RankSuf^{-1}[Suf[Posx] + 1]</tex>|proof=Рассмотрим пару суффиксов, соседних в массиве <tex>Suf</tex>. Тогда если их значение <tex>LCP</tex> больше <tex>1</tex>, то можно удалить первый символ этих суффиксов и их лексикографический порядок относительно друг друга сохранится. То есть строка <tex>S_{Suf[x] + 1}</tex> будет идти следом за строкой <tex>S_{Suf[x-1]+ 1}</tex>и останется лексикографически больше нее.

|id = fact3|about= №3|statement=Если <tex>LCP(A_S_{PosSuf[x-1]} , A_S_{PosSuf[x]} ) > 1</tex>, тогда <tex>LCP(A_S_{PosSuf[x-1]+1} , A_S_{PosSuf[x]+1}) = LCP(A_S_{PosSuf[x-1]} , A_S_{PosSuf[x]} ) - 1</tex>|proof=В этом же случае, значение <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>.

===Пример===[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к утверждениям 2 и 3]]Рассмотрим строку <tex>S = aabaaca\$</tex>. Её суффиксный массив:{| class="wikitable"|-!<tex>i</tex>| <tex>0</tex> || <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex>|-!<tex>Suf[i]</tex>| <tex>7</tex> || <tex>6</tex> || <tex>0</tex> || <tex>3</tex> || <tex>1</tex> || <tex>4</tex> || <tex>2</tex> || <tex>5</tex>|}Распишем суффиксный массив по столбикам для удобного нахождения <tex>LCP</tex>:{| class="wikitable"|-!<tex>i</tex>| <tex>0</tex> || <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex>|-!<tex>Suf[i]</tex>| <tex>7</tex> || <tex>6</tex> || <tex>0</tex> || <tex>3</tex> || <tex>1</tex> || <tex>4</tex> || <tex>2</tex> || <tex>5</tex>|-!<tex>0</tex>| <tex>\$</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>b</tex> || <tex>c</tex>|-!<tex>1</tex>| || <tex>\$</tex> || <tex>a</tex> || <tex>a</tex> || <tex>b</tex> || <tex>c</tex> || <tex>a</tex> || <tex>a</tex>|-!<tex>2</tex>| || || <tex>b</tex> || <tex>c</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>\$</tex>|-!<tex>3</tex>| || || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>\$</tex> || <tex>c</tex> || |-!<tex>4</tex>| || || <tex>a</tex> || <tex>\$</tex> || <tex>c</tex> || || <tex>a</tex> || |-!<tex>5</tex>| || || <tex>c</tex> || || <tex>a</tex> || || <tex>\$</tex> || |-!<tex>6</tex>| || || <tex>a</tex> || || <tex>\$</tex> || || || |-!<tex>7</tex>| || || <tex>\$</tex> || || || || || |}Строим массив <tex>LCP</tex>:{| class="wikitable"|-!<tex>i</tex>| <tex>0</tex> || <tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex>|-!<tex>lcp[i]</tex>| <tex>\bot</tex> || <tex>0</tex> || <tex>1</tex> || <tex>2</tex> || <tex>1</tex> || <tex>1</tex> || <tex>0</tex> || <tex>0</tex>|}Например <tex>lcp[3] = 2</tex> {{---}} длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</tex>.===Вспомогательные утверждения=== Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>A_S_{i}</tex> и его смежным соседним суффиксом в массиве <tex>PosSuf</tex>, при условии, что значение <tex>LCP</tex> между <tex>A_S_{i-1}</tex> и его смежным соседним суффиксом известны. Для удобства записи пусть <tex>p=RankSuf^{-1}[i - 1]</tex> и <tex>q = RankSuf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = PosSuf[p-1]</tex> и <tex>k = PosSuf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>Heightlcp[q]</tex>, когда задано <tex>Heightlcp[p]</tex>.

{{Лемма|id = lemma|statement=Если <tex>LCP(A_S_{j-1}, A_S_{i-1}) > 1</tex>, тогда <tex>LCP(A_kS_k,A_iS_i) \le geqslant LCP(A_jS_j,A_iS_i)</tex>.

Так как <tex>LCP(A_S_{j−1j-1},A_S_{i−1i-1}) > 1</tex>, имеем <tex>RankSuf^{-1}[j] < RankSuf^{-1}[i]</tex> из факта [[#fact2 | утверждения №2]]. Так как <tex>RankSuf^{-1}[j] \le Rankleqslant Suf^{-1}[k] = RankSuf^{-1}[i] - 1</tex>, имеем <tex>LCP(A_S_{k} , A_S_{i}) \ge geqslant LCP(A_S_{j} , A_S_{i})</tex> из факта [[#fact1 | утверждения №1]].

Если <tex>Heightlcp[p] = lcpLCP(A_S_{j-1}, A_S_{i-1}) > 1</tex>, то <tex>Heightlcp[q] = lcpLCP(A_S_{k}, A_S_{i}) \ge Heightgeqslant lcp[p] - 1</tex>

<tex>LCP(A_S_{k}, A_S_{i}) \ge geqslant LCP(A_S_{j} , A_S_{i})</tex>(из Леммыпо [[#lemma | лемме]]) = . <tex>LCP(A_S_{j} , S_{i}) = LCP(S_{j-1}, A_S_{i−1i-1}) - 1</tex> (из факта по [[#fact3 | утверждению №3]]). Значит, <tex>LCP(S_{k}, S_{i})\geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex>.

==Описание алгоритмаАлгоритм==Представим алгоритм <tex>\mathrm{buildLCP}</tex> который вычисляет массив <tex>LCP</tex>, зная суффиксный массив. Исходя из выше написанной теоремы, нам не нужно сравнивать все символы, когда мы вычисляем <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf^{-1}</tex>. Чтобы вычислить <tex>LCP</tex> всех соседних суффиксов в массиве <tex>Suf^{-1}</tex> эффективно, будем рассматривать суффиксы по порядку начиная с <tex>S_1</tex> и заканчивая <tex>S_n</tex>. ===Псевдокод===Алгоритм принимает на вход строку длиной <tex>n</tex>, с добавленным специальным символом <tex>\$</tex> и суффиксный массив этой строки, и возвращает массив <tex>lcp</tex>. '''int[]''' buildLCP(str: '''string''', suf: '''int[]''') '''int''' n <tex>=</tex> str.length '''int[len]''' lcp '''int[len]''' pos <font color=green> // pos[] {{---}} массив, обратный массиву suf </font> '''for''' i = 0 '''to''' n - 1 pos[suf[i]] <tex>=</tex> i '''int''' k <tex>=</tex> 0 '''for''' i = 0 '''to''' n - 1 '''if''' k > 0 k-- '''if''' pos[i] == n - 1 lcp[n - 1] <tex>=</tex> -1 k <tex>=</tex> 0 '''continue''' '''else''' '''int''' j <tex>=</tex> suf[pos[i] + 1] '''while''' max(i + k, j + k) < n '''and''' str[i + k] == str[j + k] k++ lcp[pos[i]] <tex>=</tex> k '''return''' lcp ===Асимптотика===Таким образом, начиная проверять <tex>lcpLCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>lcpLCP</tex>.Покажем, что построение <tex>lcpLCP</tex> таким образом действительно требует <tex>O(Nn)</tex> времени. Действительно, на каждой итерации текущее значение <tex>lcpLCP</tex> может быть не болеечем на единицу меньше предыдущего. Таким образом, значения <tex>lcpLCP</tex> в сумме могут увеличиться не более, чем на <tex>2N2n</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>lcpLCP</tex> за <tex>O(Nn)</tex>. == См. также ==* [[Алгоритм цифровой сортировки суффиксов циклической строки]]

==Источникиинформации==1. * [[httpwikipedia://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].