Алгоритм Касаи и др. — различия между версиями

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

Версия 13:00, 22 июня 2011

Алгоритм Касаи (Аримуры-Арикавы-Касаи-Ли-Парка) — алгоритм, позволяющий за линейное время вычислить значения наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом порядке (largest common prefix, далее [math]lcp[/math]).

Обозначения

[math]S[/math] — данная строка.

[math]height[i][/math] — длина наибольшего общего префикса [math]i[/math] и [math]i-1[/math] строк в суффиксном массиве ([math]suf[i][/math] и [math]suf[i-1][/math] соответственно).

[math]suf^{-1}[/math] — обратный суффиксный массив, удовлетворяющий свойству [math]suf^{-1}[suf[i]] = i[/math]. Может быть построен одним линейным проходом по суффиксному массиву.

Все массивы и строка имеют 0-индексацию.

Описание алгоритма

Значения [math]height[/math] считаются для все суффиксов строки последовательно. Значение [math]height[suf^{-1}[1]][/math] считается наивным методом за линейное время. Покажем, как вычислить [math]height[suf^{-1}[i]][/math], если значение [math]height[suf^{-1}[i-1]][/math] известно.

Теорема:
Если [math]height[suf^{-1}[i-1]] \gt 0[/math], то [math]height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1[/math]. Доказательство
Доказательство:
[math]\triangleright[/math]

[math]height[suf^{-1}[i-1]] = lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]})[/math], [math]height[suf^{-1}[i]] = lcp(S_{i}, S_{suf[suf^{-1}[{i}]-1]})[/math]. Рассмотрим суффиксный массив и позиции в нем суффиксов [math]i, i-1, suf[suf^{-1}[{i-1}-1][/math]: так как [math]i-1[/math] и [math]i[/math] суффикс отличаются только первым символом, как и [math]suf[suf^{-1}[{i-1}]-1][/math] с [math]suf[suf^{-1}[{i-1}]-1] + 1[/math], то [math]lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(i-1, suf[suf^{-1}[{i-1}]-1]) - 1[/math]. Так как суффикс [math]suf[suf^{-1}[{i-1}]-1][/math] в суффиксном массиве предшествует суффиксу [math]i-1[/math], то суффикс [math]suf[suf^{-1}[{i-1}]-1] + 1[/math] будет предшествовать суффиксу [math]i[/math] (но необязательно будет непоредственно предыдущим), то [math]height[suf^{-1}[i]] \ge lcp(i, suf[suf^{-1}[{i-1}]-1] + 1)[/math], [math]lcp(i, suf[suf^{-1}[{i-1}]-1] + 1) \ge lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) - 1[/math],

[math]lcp(S_{i-1}, S_{suf[suf^{-1}[{i-1}]-1]}) = height[suf^{-1}[i-1]][/math], откуда [math]height[suf^{-1}[i]] \ge height[suf^{-1}[i-1]] - 1[/math].
[math]\triangleleft[/math]

Источники

1. Алгоритм Касаи.
2. T.Kasai, G.Lee, H.Arimura, S.Arikawa, K.Park - Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Application.