137
правок
Изменения
м
Нет описания правки
==Некоторые свойства <tex>LCP</tex>==
===Факт №1===
<tex>LCP</tex> между двумя суффиксами {{---}} это минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min_{x < y \le leqslant z}(LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.
Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.
{{Утверждение
|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \ge geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \le leqslant z</tex>
}}
{{Лемма|statement=
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \ge 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> из факта №2. Так как <tex>Suf^{-1}[j] \le leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \ge geqslant LCP(S_{j} , S_{i})</tex> из факта №1
}}
{{Теорема|statement=
Если <tex>Height[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>Height[q] = LCP(S_{k}, S_{i}) \ge geqslant Height[p] - 1</tex>
|proof=
<tex>LCP(S_{k}, S_{i}) \ge geqslant LCP(S_{j} , S_{i})</tex>(из Леммылеммы) = <tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта №3). Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex>
}}
чем на единицу меньше предыдущего. Таким образом, значения <tex>LCP</tex> в сумме могут увеличиться не более, чем на <tex>2N</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>LCP</tex> за <tex>O(N)</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].
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Суффиксный массив]]
