Изменения

'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''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</tex>.* Массив, обратный суффиксному, <tex>Suf^{-1}</tex>{{---}} массив, обратный суффиксному, который может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>. Пусть у нас есть массив * <tex>lcp</tex>LCP(S_{Suf[x]}, такой что <tex>lcpS_{Suf[iz]})</tex> {{---}} длина наибольшего общего префикса строк <tex>iS_{Suf[x]}</tex> и <tex>i-1S_{Suf[z]}</tex> строк в суффиксном массиве (.* <tex>Suflcp[i]</tex> и {{---}} длина наибольшего общего префикса соседних строк, то есть <tex>lcp[i] = LCP(S_{Suf[i-1]}, S_{Suf[i]})</tex> соответственно).

|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \leqslant z</tex>}}|proof=

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

{{Лемма|id = lemma|statement=

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