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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Описание алгоритма и псевдокод)
м (rollbackEdits.php mass rollback)
 
(не показано 18 промежуточных версий 6 участников)
Строка 1: Строка 1:
'''Алгоритм Касаи''' (Аримуры-Арикавы-Касаи-Ли-Парка) {{---}} алгоритм, позволяющий за линейное время вычислить
+
'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.
длину наибольших общих префиксов для соседних циклических сдвигов строки, отсортированных в лексикографическом
 
порядке (largest common prefix, далее <tex>LCP</tex>).
 
  
 
==Обозначения==
 
==Обозначения==
Задана строка <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>S</tex> {{---}} данная строка.
 +
* <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе.
 +
* <tex>Suf</tex> {{---}} [[Суффиксный массив | суффиксный массив]].
 +
* <tex>Suf^{-1}</tex> {{---}} массив, обратный суффиксному, который может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
 +
* <tex>LCP(S_{Suf[x]}, S_{Suf[z]})</tex> {{---}} длина наибольшего общего префикса строк <tex>S_{Suf[x]}</tex> и <tex>S_{Suf[z]}</tex>.
 +
* <tex>lcp[i]</tex> {{---}} длина наибольшего общего префикса соседних строк <tex>i-1</tex> и <tex>i</tex>, то есть <tex>lcp[i] = LCP(S_{Suf[i-1]}, S_{Suf[i]})</tex>.
  
<tex>Height[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).
+
==Некоторые свойства LCP==
 
+
{{Утверждение
==Некоторые свойства <tex>LCP</tex>==
+
|id = fact1
===Факт №1===
+
|about= №1
<tex>LCP</tex> между двумя суффиксами {{---}} это минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min_{x < y \leqslant z}(LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.
+
|statement=
 +
<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \leqslant z</tex>
 +
|proof=
 +
<tex>LCP</tex> между двумя суффиксами {{---}} минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{x < y \leqslant z}LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.
 
Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.
 
Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.
 
{{Утверждение
 
|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \leqslant z</tex>
 
 
}}
 
}}
 
+
Также заметим, что <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{i = x + 1 \ldots z}lcp[i]</tex>.
===Факт №2===
 
Если значение <tex>LCP</tex> между парой суффиксов, соседних в массиве <tex>Suf</tex>, больше <tex>1</tex>, то можно удалить первый символ каждого суффикса и лексикографический порядок суффиксов сохранится.<br>
 
 
{{Утверждение
 
{{Утверждение
 +
|id = fact2
 +
|about= №2
 
|statement=
 
|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>
+
Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]}) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 1]</tex>
 +
|proof=
 +
Рассмотрим пару суффиксов, соседних в массиве <tex>Suf</tex>. Тогда если их значение <tex>LCP</tex> больше <tex>1</tex>, то можно удалить первый символ этих суффиксов и их лексикографический порядок относительно друг друга сохранится. То есть строка <tex>S_{Suf[x] + 1}</tex> будет идти следом за строкой <tex>S_{Suf[x-1] + 1}</tex> и останется лексикографически больше нее.
 
}}
 
}}
[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к факту 2 и 3]]
 
  
===Факт №3===
 
В этом же случае, значение <tex>LCP</tex> между <tex>S_{Suf[x-1]+1}</tex> и <tex>S_{Suf[x]+1}</tex> на один меньше значения <tex>LCP</tex> между <tex>S_{Suf[x-1]}</tex> и <tex>S_{Suf[x]}</tex>.<br>
 
 
{{Утверждение
 
{{Утверждение
 +
|id = fact3
 +
|about= №3
 
|statement=Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>LCP(S_{Suf[x-1]+1} , S_{Suf[x]+1}) = LCP(S_{Suf[x-1]} , S_{Suf[x]} ) - 1</tex>
 
|statement=Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>LCP(S_{Suf[x-1]+1} , S_{Suf[x]+1}) = LCP(S_{Suf[x-1]} , S_{Suf[x]} ) - 1</tex>
 +
|proof=
 +
В этом же случае, значение <tex>LCP</tex> между <tex>S_{Suf[x-1]+1}</tex> и <tex>S_{Suf[x]+1}</tex> на один меньше значения <tex>LCP</tex> между <tex>S_{Suf[x-1]}</tex> и <tex>S_{Suf[x]}</tex>.
 
}}
 
}}
  
 +
===Пример===
 +
[[Файл: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>lcp[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>lcp[3] = 2</tex> {{---}} длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</tex>.
 
===Вспомогательные утверждения===
 
===Вспомогательные утверждения===
  
Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>Height[q]</tex>, когда задано <tex>Height[p]</tex>
+
Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>lcp[q]</tex>, когда задано <tex>lcp[p]</tex>.
  
{{Лемма|statement=
+
{{Лемма
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>
+
|id = lemma
 +
|statement=
 +
Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>.
 
|proof=
 
|proof=
Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из факта №2. Так как <tex>Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> из факта №1
+
Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из [[#fact2 | утверждения №2]]. Так как <tex>Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> из [[#fact1 | утверждения №1]].
 
}}
 
}}
  
 
{{Теорема|statement=
 
{{Теорема|statement=
Если <tex>Height[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>Height[q] = LCP(S_{k}, S_{i}) \geqslant Height[p] - 1</tex>
+
Если <tex>lcp[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>lcp[q] = LCP(S_{k}, S_{i}) \geqslant lcp[p] - 1</tex>
 
|proof=
 
|proof=
<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (из леммы)
+
<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (по [[#lemma | лемме]]).
  
<tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта №3).
+
<tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (по [[#fact3 | утверждению №3]]).
  
Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex>  
+
Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex>.
 
}}
 
}}
  
==Описание алгоритма и псевдокод==
+
==Алгоритм==
Таким образом, начиная проверять <tex>LCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>LCP</tex>.
+
Представим алгоритм <tex>\mathrm{buildLCP}</tex> который вычисляет массив <tex>LCP</tex>, зная суффиксный массив. Исходя из выше написанной теоремы, нам не нужно сравнивать все символы, когда мы вычисляем <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf^{-1}</tex>. Чтобы вычислить <tex>LCP</tex> всех соседних суффиксов в массиве <tex>Suf^{-1}</tex> эффективно, будем рассматривать суффиксы по порядку начиная с <tex>S_1</tex> и заканчивая <tex>S_n</tex>.
Покажем, что построение <tex>LCP</tex> таким образом действительно требует <tex>O(N)</tex> времени. Действительно, на каждой итерации текущее значение <tex>LCP</tex> может быть не более
 
чем на единицу меньше предыдущего. Таким образом, значения <tex>LCP</tex> в сумме могут увеличиться не более, чем на <tex>2N</tex> (с точностью до константы). Следовательно, алгоритм построит <tex>LCP</tex> за <tex>O(N)</tex>.
 
 
 
 
    
 
    
  '''int[]''' buildLCP(str : '''string''', suf : '''int[]''') <font color=green> // str {{---}} исходная строка с добавленным специальным символом $ </font>
+
===Псевдокод===
                                            <font color=green> // suf[] {{---}} суффиксный массив строки str </font>
+
Алгоритм принимает на вход строку длиной <tex>n</tex>, с добавленным специальным символом <tex>\$</tex> и суффиксный массив этой строки, и возвращает массив <tex>lcp</tex>.
     '''int''' len <tex>\leftarrow</tex> str.length
+
  '''int[]''' buildLCP(str: '''string''', suf: '''int[]''')
 +
     '''int''' n <tex>=</tex> str.length
 
     '''int[len]''' lcp
 
     '''int[len]''' lcp
     '''int[len]''' pos                           <font color=green> // pos[] {{---}} массив, обратный массиву suf </font>
+
     '''int[len]''' pos <font color=green> // pos[] {{---}} массив, обратный массиву suf </font>
     '''for''' i = 0 '''to''' len - 1
+
     '''for''' i = 0 '''to''' n - 1
       pos[suf[i]] <tex>\leftarrow</tex> i
+
       pos[suf[i]] <tex>=</tex> i
     '''int''' k <tex>\leftarrow</tex> 0
+
     '''int''' k <tex>=</tex> 0
     '''for''' i = 0 '''to''' len - 1
+
     '''for''' i = 0 '''to''' n - 1
 
       '''if''' k > 0
 
       '''if''' k > 0
 
           k--   
 
           k--   
       '''if''' pos[i] == len - 1
+
       '''if''' pos[i] == n - 1
           lcp[len - 1] <tex>\leftarrow</tex> -1
+
           lcp[n - 1] <tex>=</tex> -1
           k <tex>\leftarrow</tex> 0
+
           k <tex>=</tex> 0
 +
          '''continue'''
 
       '''else'''
 
       '''else'''
           '''int''' j <tex>\leftarrow</tex> suf[pos[i] + 1]
+
           '''int''' j <tex>=</tex> suf[pos[i] + 1]
           '''while''' max(i + k, j + k) < len '''and''' str[i + k] == str[j + k]
+
           '''while''' max(i + k, j + k) < n '''and''' str[i + k] == str[j + k]
 
             k++
 
             k++
           lcp[pos[i]] <tex>\leftarrow</tex> k
+
           lcp[pos[i]] <tex>=</tex> k
 
     '''return''' lcp
 
     '''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>.
 +
 +
== См. также ==
 +
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 19:35, 4 сентября 2022

Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка (англ. Kasai, Arimura, Arikawa, Lee, Park algorithm) — алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. longest common prefix, LCP) для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.

Обозначения

Введём следующие обозначения:

  • [math]S[/math] — данная строка.
  • [math]S_{i}[/math] — суффикс строки [math]S[/math], начинающийся в [math]i[/math]-ом символе.
  • [math]Suf[/math] суффиксный массив.
  • [math]Suf^{-1}[/math] — массив, обратный суффиксному, который может быть получен немедленно, если задан массив [math]Suf[/math]. Если [math]Suf[k] = i[/math], то [math]Suf^{-1}[i] = k[/math].
  • [math]LCP(S_{Suf[x]}, S_{Suf[z]})[/math] — длина наибольшего общего префикса строк [math]S_{Suf[x]}[/math] и [math]S_{Suf[z]}[/math].
  • [math]lcp[i][/math] — длина наибольшего общего префикса соседних строк [math]i-1[/math] и [math]i[/math], то есть [math]lcp[i] = LCP(S_{Suf[i-1]}, S_{Suf[i]})[/math].

Некоторые свойства LCP

Утверждение (№1):
[math]LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x \lt y \leqslant z[/math]
[math]\triangleright[/math]

[math]LCP[/math] между двумя суффиксами — минимум [math]LCP[/math] всех пар соседних суффиксов между ними в суффиксном массиве [math]Suf[/math]. То есть [math]LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{x \lt y \leqslant z}LCP(S_{Suf[y - 1]},S_{Suf[y]})[/math].

Отсюда следует, что [math]LCP[/math] пары соседних суффиксов в массиве [math]Suf[/math] больше или равно [math]LCP[/math] пары суффиксов, окружающих их.
[math]\triangleleft[/math]

Также заметим, что [math]LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{i = x + 1 \ldots z}lcp[i][/math].

Утверждение (№2):
Если [math]LCP(S_{Suf[x-1]} , S_{Suf[x]}) \gt 1[/math], тогда [math]Suf^{-1}[Suf[x - 1] + 1] \lt Suf^{-1}[Suf[x] + 1][/math]
[math]\triangleright[/math]
Рассмотрим пару суффиксов, соседних в массиве [math]Suf[/math]. Тогда если их значение [math]LCP[/math] больше [math]1[/math], то можно удалить первый символ этих суффиксов и их лексикографический порядок относительно друг друга сохранится. То есть строка [math]S_{Suf[x] + 1}[/math] будет идти следом за строкой [math]S_{Suf[x-1] + 1}[/math] и останется лексикографически больше нее.
[math]\triangleleft[/math]
Утверждение (№3):
Если [math]LCP(S_{Suf[x-1]} , S_{Suf[x]} ) \gt 1[/math], тогда [math]LCP(S_{Suf[x-1]+1} , S_{Suf[x]+1}) = LCP(S_{Suf[x-1]} , S_{Suf[x]} ) - 1[/math]
[math]\triangleright[/math]
В этом же случае, значение [math]LCP[/math] между [math]S_{Suf[x-1]+1}[/math] и [math]S_{Suf[x]+1}[/math] на один меньше значения [math]LCP[/math] между [math]S_{Suf[x-1]}[/math] и [math]S_{Suf[x]}[/math].
[math]\triangleleft[/math]

Пример

Пояснительная картинка к утверждениям 2 и 3

Рассмотрим строку [math]S = aabaaca\$[/math]. Её суффиксный массив:

[math]i[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math]
[math]Suf[i][/math] [math]7[/math] [math]6[/math] [math]0[/math] [math]3[/math] [math]1[/math] [math]4[/math] [math]2[/math] [math]5[/math]

Распишем суффиксный массив по столбикам для удобного нахождения [math]LCP[/math]:

[math]i[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math]
[math]Suf[i][/math] [math]7[/math] [math]6[/math] [math]0[/math] [math]3[/math] [math]1[/math] [math]4[/math] [math]2[/math] [math]5[/math]
[math]0[/math] [math]\$[/math] [math]a[/math] [math]a[/math] [math]a[/math] [math]a[/math] [math]a[/math] [math]b[/math] [math]c[/math]
[math]1[/math] [math]\$[/math] [math]a[/math] [math]a[/math] [math]b[/math] [math]c[/math] [math]a[/math] [math]a[/math]
[math]2[/math] [math]b[/math] [math]c[/math] [math]a[/math] [math]a[/math] [math]a[/math] [math]\$[/math]
[math]3[/math] [math]a[/math] [math]a[/math] [math]a[/math] [math]\$[/math] [math]c[/math]
[math]4[/math] [math]a[/math] [math]\$[/math] [math]c[/math] [math]a[/math]
[math]5[/math] [math]c[/math] [math]a[/math] [math]\$[/math]
[math]6[/math] [math]a[/math] [math]\$[/math]
[math]7[/math] [math]\$[/math]

Строим массив [math]LCP[/math]:

[math]i[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math]
[math]lcp[i][/math] [math]\bot[/math] [math]0[/math] [math]1[/math] [math]2[/math] [math]1[/math] [math]1[/math] [math]0[/math] [math]0[/math]

Например [math]lcp[3] = 2[/math] — длина наибольшего общего префикса [math]aa[/math] суффиксов [math]S_{Suf[2]} = aabaaca\$[/math] и [math]S_{Suf[3]} = aaca\$[/math].

Вспомогательные утверждения

Теперь рассмотрим следующую задачу: рассчитать [math]LCP[/math] между суффиксом [math]S_{i}[/math] и его соседним суффиксом в массиве [math]Suf[/math], при условии, что значение [math]LCP[/math] между [math]S_{i-1}[/math] и его соседним суффиксом известны. Для удобства записи пусть [math]p=Suf^{-1}[i - 1][/math] и [math]q = Suf^{-1}[i][/math]. Так же пусть [math]j - 1 = Suf[p-1][/math] и [math]k = Suf[q - 1][/math]. Проще говоря, мы хотим посчитать [math]lcp[q][/math], когда задано [math]lcp[p][/math].

Лемма:
Если [math]LCP(S_{j-1}, S_{i-1}) \gt 1[/math], тогда [math]LCP(S_k,S_i) \geqslant LCP(S_j,S_i)[/math].
Доказательство:
[math]\triangleright[/math]
Так как [math]LCP(S_{j-1},S_{i-1}) \gt 1[/math], имеем [math]Suf^{-1}[j] \lt Suf^{-1}[i][/math] из утверждения №2. Так как [math]Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1[/math], имеем [math]LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})[/math] из утверждения №1.
[math]\triangleleft[/math]
Теорема:
Если [math]lcp[p] = LCP(S_{j-1}, S_{i-1}) \gt 1[/math], то [math]lcp[q] = LCP(S_{k}, S_{i}) \geqslant lcp[p] - 1[/math]
Доказательство:
[math]\triangleright[/math]

[math]LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})[/math] (по лемме).

[math]LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1[/math] (по утверждению №3).

Значит, [math]LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1[/math].
[math]\triangleleft[/math]

Алгоритм

Представим алгоритм [math]\mathrm{buildLCP}[/math] который вычисляет массив [math]LCP[/math], зная суффиксный массив. Исходя из выше написанной теоремы, нам не нужно сравнивать все символы, когда мы вычисляем [math]LCP[/math] между суффиксом [math]S_{i}[/math] и его соседним суффиксом в массиве [math]Suf^{-1}[/math]. Чтобы вычислить [math]LCP[/math] всех соседних суффиксов в массиве [math]Suf^{-1}[/math] эффективно, будем рассматривать суффиксы по порядку начиная с [math]S_1[/math] и заканчивая [math]S_n[/math].

Псевдокод

Алгоритм принимает на вход строку длиной [math]n[/math], с добавленным специальным символом [math]\$[/math] и суффиксный массив этой строки, и возвращает массив [math]lcp[/math].

int[] buildLCP(str: string, suf: int[])
   int n [math]=[/math] str.length
   int[len] lcp
   int[len] pos   // pos[] — массив, обратный массиву suf 
   for i = 0 to n - 1
      pos[suf[i]] [math]=[/math] i
   int k [math]=[/math] 0
   for i = 0 to n - 1
      if k > 0
         k--  
      if pos[i] == n - 1
         lcp[n - 1] [math]=[/math] -1
         k [math]=[/math] 0
         continue
      else
         int j [math]=[/math] suf[pos[i] + 1]
         while max(i + k, j + k) < n and str[i + k] == str[j + k]
            k++
         lcp[pos[i]] [math]=[/math] k
   return lcp

Асимптотика

Таким образом, начиная проверять [math]LCP[/math] для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить [math]LCP[/math]. Покажем, что построение [math]LCP[/math] таким образом действительно требует [math]O(n)[/math] времени. Действительно, на каждой итерации текущее значение [math]LCP[/math] может быть не более чем на единицу меньше предыдущего. Таким образом, значения [math]LCP[/math] в сумме могут увеличиться не более, чем на [math]2n[/math] (с точностью до константы). Следовательно, алгоритм построит [math]LCP[/math] за [math]O(n)[/math].

См. также

Источники информации