Изменения
Нет описания правки
'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''algorithm of Kasai, Arimura, Arikawa, Lee, Parkalgorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить
длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для соседних циклических сдвигов строки, отсортированных в лексикографическом
порядке.
==Обозначения==
Пусть <tex>\mathrm{Height}</tex> {{---}} у нас есть массив <tex>LCPlcp</tex>, тогда такой что <tex>\mathrm{Height}lcp[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\limits_{x < y \leqslant z}LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.
==Некоторые свойства LCP==
{{Утверждение
|id = fact1
|about= №1
|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \leqslant z</tex>
}}
<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> пары суффиксов, окружающих их.
{{Утверждение
|id = fact2
|about= №2
|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>
}}
Рассмотрим пару суффиксов, соседних в массиве <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(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_{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>.
===Пример===
| <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>\mathrm{Height}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>\mathrm{Height}lcp[3] = 2</tex> {{---}} это длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</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{Heightlcp}[q]</tex>, когда задано <tex>\mathrm{Heightlcp}[p]</tex>.
{{Лемма|statement=
{{Теорема|statement=
Если <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>
|proof=
<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (из леммыпо лемме).
<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>n</tex>, с добавленным специальным символом <tex>\$</tex> и суффиксный массив этой строки, и возвращает массив <tex>lcp</tex>, такой что <tex>lcp[i]</tex> содержит длину наибольшего общего префикса строк <tex>i</tex> и <tex>i-1</tex> в суффиксном массиве.
'''int[]''' buildLCP(str: '''string''', suf: '''int[]''')
'''int''' len n <tex>=</tex> str.length
'''int[len]''' lcp
'''int[len]''' pos <font color=green> // pos[] {{---}} массив, обратный массиву suf </font>
'''for''' i = 0 '''to''' len n - 1
pos[suf[i]] <tex>=</tex> i
'''int''' k <tex>=</tex> 0
'''for''' i = 0 '''to''' len n - 1
'''if''' k > 0
k--
'''if''' pos[i] == len n - 1 lcp[len n - 1] <tex>=</tex> -1
k <tex>=</tex> 0
'''else'''
'''int''' j <tex>=</tex> suf[pos[i] + 1]
'''while''' max(i + k, j + k) < len n '''and''' str[i + k] == str[j + k]
k++
lcp[pos[i]] <tex>=</tex> k
===Асимптотика===
Таким образом, начиная проверять <tex>LCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>LCP</tex>. Покажем, что построение <tex>LCP</tex> таким образом действительно требует <tex>O(Nn)</tex> времени. Действительно, на каждой итерации текущее значение <tex>LCP</tex> может быть не болеечем на единицу меньше предыдущего. Таким образом, значения <tex>LCP</tex> в сумме могут увеличиться не более, чем на <tex>2N2n</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>LCP</tex> за <tex>O(Nn)</tex>.
== См. также ==
