Изменения
Нет описания правки
'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних циклических сдвигов суффиксов строки, отсортированных в лексикографическом порядке.
==Обозначения==
* <tex>Suf^{-1}</tex> {{---}} массив, обратный суффиксному, который может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
* <tex>LCP(S_{Suf[x]}, S_{Suf[z]})</tex> {{---}} длина наибольшего общего префикса строк <tex>S_{Suf[x]}</tex> и <tex>S_{Suf[z]}</tex>.
* <tex>lcp[i]</tex> {{---}} длина наибольшего общего префикса соседних строк<tex>i-1</tex> и <tex>i</tex>, то есть <tex>lcp[i] = LCP(S_{Suf[i-1]}, S_{Suf[i]})</tex>.
==Некоторые свойства LCP==
===Пример===
[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к факту утверждениям 2 и 3]]
Рассмотрим строку <tex>S = aabaaca\$</tex>. Её суффиксный массив:
{| class="wikitable"
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant 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> из факта [[#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]].
}}
