Изменения
Нет описания правки
'''Алгоритм Касаи''' (Аримуры-Арикавы-Касаи-Ли-Парка) {{---}} алгоритм, позволяющий за линейное время вычислить
значения наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом
порядке (largest common prefix, далее <tex>lcpLCP</tex>).
==Обозначения==
Задана строка <tex>SA</tex>. Тогда <tex>A_{i}</tex> {{---}} данная строкасуфикс строки <tex>A</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суфиксный массив <tex>Pos</tex>. Для вычисления <tex>LCP</tex> будем использовать промежуточный массив <tex>Rank</tex>. Массив <tex>Rank</tex> определен как обратный к массиву <tex>Pos</tex>. Он может быть получен немедленно, если задан массив <tex>Pos</tex>. Если <tex>Pos[k] = i</tex>, то <tex>Rank[i] = k</tex>.
<tex>heightHeight[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>sufPos[i]</tex> и <tex>sufPos[i-1]</tex> соответственно).
==Некоторые свойства <tex>LCP</tex>suf^{-1}=====Факт №1===<tex>LCP</tex> между двумя суфиксами {{---}} обратный суффиксный массив, удовлетворяющий свойству это минимум <tex>LCP</tex> всех пар смежных суфиксов между ними в суфиксном массиве <tex>Pos</tex>. То есть <tex>suf^LCP(A_{Pos[x]}, A_{Pos[z]}) = min_{x < y \le z}(LCP(A_{Pos[y -1]},A_{Pos[suf[iy]] = i})</tex>.Может быть построен одним линейным проходом по суффиксному массивуОтсюда следует, что <tex>LCP</tex> пары соседних суфиксов в массиве <tex>Pos</tex> больше или равно <tex>LCP</tex> пары суфиксов, окружающих их.
==Описание алгоритма=Факт №2===Значения Если значение <tex>heightLCP</tex> считаются для всех между парой соседних суфиксов, смежных в массиве <tex>Pos</tex> больше <tex>1</tex>, то лексикографический порядок суффиксов строки последовательносохранится, если удалить первый символ каждого суффикса. Значение <br>{{Утверждение|statement=Если <tex>heightLCP(A_{Pos[suf^x-1]} , A_{Pos[x]} ) > 1</tex>, тогда <tex>Rank[Pos[x -1] + 1] < Rank[Pos[x] + 1]</tex>}}===Факт №3===В этом же случае, значение <tex>LCP</tex> между <tex>A_{Pos[0x-1]+1}</tex> и <tex>A_{Pos[x]+1}</tex> на один меньше значения <tex>LCP</tex> между <tex>A_{Pos[x-1]}</tex> и <tex>A_{Pos[x]}</tex> считается .<br>наивным методом за линейное время. Покажем{{Утверждение|statement=Если <tex>LCP(A_{Pos[x-1]} , A_{Pos[x]} ) > 1</tex>, как вычислить тогда <tex>heightLCP(A_{Pos[suf^x-1]+1} , A_{Pos[x]+1}) = LCP(A_{Pos[x-1]} , A_{Pos[x]} ) - 1</tex>}} Теперь рассмотрим следующую задачу: расчитать <tex>LCP</tex> между суфиксом <tex>A_{i}</tex> и его смежным суфиксом в массиве <tex>Pos</tex>, при условии, что значение <tex>LCP</tex> между <tex>A_{i-1}</tex> и его смежным суфиксом известны. Для удобства записи пусть <tex>p=Rank[i - 1]</tex> и <tex>q = Rank[i]</tex>. Так же пусть <tex>j - 1 = Pos[p-1]</tex> и <tex>k = Pos[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>Height[q]</tex>, если значение когда задано <tex>heightHeight[suf^p]</tex> {{Лемма|statement=Если <tex>LCP(A_{j-1}[, A_{i-1}) > 1</tex>, тогда <tex>LCP(A_k,A_i) \le LCP(A_j,A_i)</tex>|proof=Так как <tex>LCP(A_{j−1},A_{i−1}) > 1</tex>, имеем <tex>Rank[j]< Rank[i]</tex>из факта №2. Так как <tex>Rank[j] \le Rank[k] = Rank[i] - 1</tex>, имеем <tex>LCP(A_{k} , A_{i}) \ge LCP(A_{j} , A_{i})</tex> из факта №1известно.}}
{{Теорема|statement=
Если <tex>heightHeight[suf^p] = lcp(A_{j-1}[, A_{i-1]] }) > 01</tex>, то <tex>heightHeight[suf^q] = lcp(A_{-1k}[, A_{i]] }) \ge heightHeight[suf^{-1}[i-1]p] - 1</tex>.
|proof=
<tex>height[suf^{-1}[i-1]] = lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]})</tex>, <tex>height[suf^{-1}[i]] = lcpLCP(S_{i}, S_{suf[suf^{-1}[{i}]-1]})</tex>.Рассмотрим суффиксный массив и позиции в нем суффиксов <tex>i, i-1, suf[suf^{-1}[{i-1}]-1]</tex>:так как <tex>i-1</tex> и <tex>i</tex> суффикс отличаются только первым символом, как и <tex>suf[suf^{-1}[{i-1}]-1]</tex> с <tex>suf[suf^A_{-1k}[{i-1}]-1] + 1</tex>, то<tex>lcp(i, suf[suf^{-1}[A_{i-1}]-1] + 1) \ge lcpLCP(i-1, suf[suf^A_{-1j}[, A_{i-1}]-1]) - 1</tex>. Так как суффикс <tex>suf[suf^{-1}[{i-1}]-1]</tex> в суффиксном массиве предшествуетсуффиксу <tex>i-1</tex>, то суффикс <tex>suf[suf^{-1}[{i-1}]-1] + 1</tex> будет предшествовать суффиксу <tex>i</tex> (но необязательно будет непосредственно предыдущимиз Леммы), то = <tex>height[suf^{-1}[i]] \ge lcpLCP(i, suf[suf^A_{j-1}[{i-1}]-1] + 1)</tex>, <tex>lcp(i, suf[suf^A_{-1}[{i-1}]-1] + 1) \ge lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]i−1}) - 1</tex>,<tex>lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}из факта №3) = height[suf^{-1}[i-1]]</tex>, откуда <tex>height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1</tex>.
}}
==Описание алгоритма==
Таким образом, начиная проверять <tex>lcp</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>lcp</tex>.
Покажем, что построение <tex>lcp</tex> таким образом действительно требует <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>lcp</tex> может быть не более
