Изменения
Нет описания правки
==Обозначения==
Задана строка <tex>S</tex>. Тогда <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив <tex>Suf</tex>. Для вычисления <tex>LCP</tex> будем использовать промежуточный вспомогательный массив <tex>Suf^{-1}</tex>. Массив <tex>Suf^{-1}</tex> определен как обратный к массиву <tex>Suf</tex>. Он может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
Пусть <tex>\mathrm{Height}</tex> {{---}} массив <tex>LCP</tex>, тогда <tex>\mathrm{Height}[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).
==Некоторые свойства <tex>LCP</tex>==
===Факт №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>
}}
===Факт №3===
}}
[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к факту 2 и 3]]
===Пример===
Рассмотрим строку <tex>S = aabaaca\$</tex>. Её суффиксный массив:
{| class="wikitable"
|-
!<tex>i</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>Suf[i]</tex>
| <tex>7</tex> || <tex>6</tex> || <tex>0</tex> || <tex>3</tex> || <tex>1</tex> || <tex>4</tex> || <tex>2</tex> || <tex>5</tex>
|}
Распишем суффиксный массив по столбикам для удобного нахождения <tex>LCP</tex>:
{| class="wikitable"
|-
!<tex>i</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>Suf[i]</tex>
| <tex>7</tex> || <tex>6</tex> || <tex>0</tex> || <tex>3</tex> || <tex>1</tex> || <tex>4</tex> || <tex>2</tex> || <tex>5</tex>
|-
!<tex>0</tex>
| <tex>\$</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>b</tex> || <tex>c</tex>
|-
!<tex>1</tex>
| || <tex>\$</tex> || <tex>a</tex> || <tex>a</tex> || <tex>b</tex> || <tex>c</tex> || <tex>a</tex> || <tex>a</tex>
|-
!<tex>2</tex>
| || || <tex>b</tex> || <tex>c</tex> || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>\$</tex>
|-
!<tex>3</tex>
| || || <tex>a</tex> || <tex>a</tex> || <tex>a</tex> || <tex>\$</tex> || <tex>c</tex> ||
|-
!<tex>4</tex>
| || || <tex>a</tex> || <tex>\$</tex> || <tex>c</tex> || || <tex>a</tex> ||
|-
!<tex>5</tex>
| || || <tex>c</tex> || || <tex>a</tex> || || <tex>\$</tex> ||
|-
!<tex>6</tex>
| || || <tex>a</tex> || || <tex>\$</tex> || || ||
|-
!<tex>7</tex>
| || || <tex>\$</tex> || || || || ||
|}
Строим массив <tex>LCP</tex>:
{| class="wikitable"
|-
!<tex>i</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}[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}[3] = 2</tex> {{---}} это длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</tex>
===Вспомогательные утверждения===
}}
==Описание алгоритма и псевдокодАлгоритм==Таким образом, начиная проверять Представим алгоритм <tex>LCP\mathrm{buildLCP}</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить который вычисляет массив <tex>LCP</tex>, зная суффиксный массив.ПокажемИсходя из выше написанной теоремы, нам не нужно сравнивать все символы, что построение когда мы вычисляем <tex>LCP</tex> таким образом действительно требует между суффиксом <tex>O(N)S_{i}</tex> времени. Действительно, на каждой итерации текущее значение и его соседним суффиксом в массиве <tex>LCPSuf^{-1}</tex> может быть не болеечем на единицу меньше предыдущего. Таким образом, значения Чтобы вычислить <tex>LCP</tex> всех соседних суффиксов в сумме могут увеличиться не более, чем на массиве <tex>2NSuf^{-1}</tex> (эффективно, будем рассматривать суффиксы по порядку начиная с точностью до константы). Следовательно, алгоритм построит <tex>LCPS_1</tex> за и заканчивая <tex>O(N)S_n</tex>.
===Псевдокод===
Алгоритм принимает на вход строку с добавленным специальным символом <tex>\$</tex> и суффиксный массив этой строки, и возвращает массив <tex>lcp</tex>, такой что <tex>lcp[i]</tex> содержит длину наибольшего общего префикса строк <tex>i</tex> и <tex>i-1</tex> в суффиксном массиве.
'''int[]''' buildLCP(str: '''string''', suf: '''int[]''') <font color=green> // str {{---}} исходная строка с добавленным специальным символом $ </font>
<font color=green> // suf[] {{---}} суффиксный массив строки str </font>
lcp[pos[i]] <tex>=</tex> k
'''return''' lcp
===Асимптотика===
Таким образом, начиная проверять <tex>LCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>LCP</tex>. Покажем, что построение <tex>LCP</tex> таким образом действительно требует <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>LCP</tex> может быть не более
чем на единицу меньше предыдущего. Таким образом, значения <tex>LCP</tex> в сумме могут увеличиться не более, чем на <tex>2N</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>LCP</tex> за <tex>O(N)</tex>.
== См. также ==
