Изменения

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

Задана строка Введём следующие обозначения:* <tex>S</tex>{{---}} данная строка. Тогда * <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть * <tex>Suf</tex> {{---}} [[Суффиксный массив | суффиксный массив]].* <tex>Suf^{-1}</tex> {{---}} массив, обратный суффиксному, который может быть получен немедленно, если задан суффиксный массив <tex>Suf</tex>. Для вычисления Если <tex>LCPSuf[k] = i</tex> будем использовать промежуточный массив , то <tex>Suf^{-1}[i] = k</tex>. Массив * <tex>LCP(S_{Suf^[x]}, S_{-1Suf[z]})</tex> определен как обратный к массиву {{---}} длина наибольшего общего префикса строк <tex>S_{Suf[x]}</tex>. Он может быть получен немедленно, если задан массив и <tex>S_{Suf[z]}</tex>. Если * <tex>Suflcp[ki] = </tex> {{---}} длина наибольшего общего префикса соседних строк <tex>i-1</tex> и <tex>i</tex>, то есть <tex>lcp[i] = LCP(S_{Suf^{[i-1]}, S_{Suf[i] = k})</tex>.

==Некоторые свойства LCP=={{Утверждение|id = fact1|about= №1|statement=<tex>\mathrmLCP(S_{HeightSuf[y - 1]}, S_{Suf[iy]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве ) \geqslant LCP(<tex>S_{Suf[ix]</tex> и <tex>},S_{Suf[i-1z]</tex> соответственно}). ==Некоторые свойства , x <tex>LCPy \leqslant z</tex>=====Факт №1==|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>.

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

Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 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> и останется лексикографически больше нее.

Теперь рассмотрим следующую задачу: рассчитать <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>\mathrm{Height}lcp[q]</tex>, когда задано <tex>\mathrm{Height}lcp[p]</tex>.

{{Лемма|id = lemma|statement=Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>.

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

Если <tex>\mathrm{Height}lcp[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>\mathrm{Height}lcp[q] = LCP(S_{k}, S_{i}) \geqslant \mathrm{Height}lcp[p] - 1</tex>

<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (из леммыпо [[#lemma | лемме]]).

<tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта по [[#fact3 | утверждению №3]]).

Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex> .

==Описание алгоритма и псевдокодАлгоритм==Таким образом, начиная проверять Представим алгоритм <tex>LCP\mathrm{buildLCP}</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить который вычисляет массив <tex>LCP</tex>, зная суффиксный массив.ПокажемИсходя из выше написанной теоремы, нам не нужно сравнивать все символы, что построение когда мы вычисляем <tex>LCP</tex> таким образом действительно требует между суффиксом <tex>O(N)S_{i}</tex> времени. Действительно, на каждой итерации текущее значение и его соседним суффиксом в массиве <tex>LCPSuf^{-1}</tex> может быть не болеечем на единицу меньше предыдущего. Таким образом, значения Чтобы вычислить <tex>LCP</tex> всех соседних суффиксов в сумме могут увеличиться не более, чем на массиве <tex>2NSuf^{-1}</tex> (эффективно, будем рассматривать суффиксы по порядку начиная с точностью до константы). Следовательно, алгоритм построит <tex>LCPS_1</tex> за и заканчивая <tex>O(N)S_n</tex>. 

===Псевдокод===Алгоритм принимает на вход строку длиной <tex>n</tex>, с добавленным специальным символом <tex>\$</tex> и суффиксный массив этой строки, и возвращает массив <tex>lcp</tex>. '''int[]''' buildLCP(str : '''string''', suf : '''int[]''') <font color=green> // str {{---}} исходная строка с добавленным специальным символом $ </font> <font color=green> // suf[] {{---}} суффиксный массив строки str </font> '''int''' len n <tex>\leftarrow=</tex> str.length

'''int[len]''' pos <font color=green> // pos[] {{---}} массив, обратный массиву suf </font> '''for''' i = 0 '''to''' len n - 1 pos[suf[i]] <tex>\leftarrow=</tex> i '''int''' k <tex>\leftarrow=</tex> 0 '''for''' i = 0 '''to''' len n - 1

'''if''' pos[i] == len n - 1 lcp[len n - 1] <tex>\leftarrow=</tex> -1 k <tex>\leftarrow=</tex> 0 '''continue'''

'''int''' j <tex>\leftarrow=</tex> suf[pos[i] + 1] '''while''' max(i + k, j + k) < len n '''and''' str[i + k] == str[j + k]

lcp[pos[i]] <tex>\leftarrow=</tex> k