Изменения
Нет описания правки
'''Алгоритм Касаи''' (Аримуры-Арикавы-Касаи-Ли-Парка) --- алгоритм, позволяющий за линейное время вычислить
значения наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом
порядке(largest common prefix, далее <tex>lcp</tex>). ==Обозначения==<tex>S - </tex> данная строка. <tex>height[i] - </tex> длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>suf[i]</tex> и <tex>suf[i-1]</tex> соответственно). <tex>suf^{-1}</tex> - обратный суффиксный массив, удовлетворяющий свойству <tex>suf^{-1}[suf[i]] = i</tex>.Может быть построен одним линейным проходом по суффиксному массиву. Все массивы и строка имеют 0-индексацию. ==Описание алгоритма==Значения <tex>height</tex> считаются для все суффиксов строки последовательно. Значение <tex>height[suf^{-1}[1]]</tex> считается наивным методом за линейное время. Покажем, как вычислить <tex>height[suf^{-1}[i]]</tex>, если значение <tex>height[suf^{-1}[i-1]]</tex>известно. {{Теорема|statement=Если <tex>height[suf^{-1}[i-1]] > 0</tex>, то <tex>height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 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]] = lcp(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^{-1}[{i-1}]-1] + 1</tex>, то<tex>lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(i-1, suf[suf^{-1}[{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 lcp(i, suf[suf^{-1}[{i-1}]-1] + 1)</tex>, <tex>lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) - 1</tex>,<tex>lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) = height[suf^{-1}[i-1]]</tex>, откуда <tex>height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1</tex>.}}
