Суффиксный массив — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Вариант для минимально возможного)
м (rollbackEdits.php mass rollback)
 
(не показана 71 промежуточная версия 6 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Cуффиксным массивом''' (англ. ''suffix array'') строки <tex>s[1 .. n]</tex> называется массив <tex>suf</tex> целых чисел от <tex>1</tex> до <tex>n</tex>, такой, что суффикс <tex>s[suf[i]..n]</tex> — <tex>i</tex>-й в лексикографическом порядке среди всех непустых суффиксов строки <tex>s</tex>.}}
+
'''Cуффиксным массивом''' (англ. ''suffix array'') строки <tex>s[1 .. n]</tex> называется массив <tex>suf</tex> целых чисел от <tex>1</tex> до <tex>n</tex>, такой, что суффикс <tex>s[suf[i]..n]</tex> — <tex>i</tex>-й в [[Лексикографический_порядок|лексикографическом]] порядке среди всех непустых суффиксов строки <tex>s</tex>.}}
  
 
== Пример ==
 
== Пример ==
Строка 11: Строка 11:
  
 
== Восстановление строки по суффиксному массиву ==
 
== Восстановление строки по суффиксному массиву ==
=== Постановка задачи ===
+
{{Задача
Дан суффиксный массив некоторой строки <tex>s</tex>, необходимо восстановить строку за время <tex>O(|s|)</tex>.
+
|definition = Дан суффиксный массив некоторой строки <tex>s</tex>, необходимо восстановить строку за время <tex>O(|s|)</tex>.
 +
}}
  
 
=== Вариант для бесконечного алфавита ===
 
=== Вариант для бесконечного алфавита ===
 
Так как наш алфавит не ограничен, можно <tex>i</tex>-й в лексикографическом порядке суффикс сопоставить с <tex>i</tex>-й буквой в алфавите.
 
Так как наш алфавит не ограничен, можно <tex>i</tex>-й в лексикографическом порядке суффикс сопоставить с <tex>i</tex>-й буквой в алфавите.
  
=== Псевдокод ===
+
==== Доказательство корректности ====
  '''string''' ('''int[]''' sa):
+
Если отсортировать суффиксы, то первые буквы будут расположены в том же порядке, как и в алфавите.
 +
 
 +
==== Псевдокод ====
 +
  '''string''' fromSuffixArrayToString('''int[]''' sa):
 
   '''for''' i = 1 '''to''' n
 
   '''for''' i = 1 '''to''' n
 
         s[sa[i]] = alphabet[i]  
 
         s[sa[i]] = alphabet[i]  
Строка 24: Строка 28:
  
 
=== Вариант для минимально возможного ===
 
=== Вариант для минимально возможного ===
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <tex>tmp</tex>, как в решении выше. Пусть, мы рассматриваем <tex>i</tex>-й в лексикографическом порядке суффикс (т.е. и i-ый символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если <tex>tmp[sa[i - 1] + 1] < tmp[sa[i] + 1]</tex>, т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.
+
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <tex>tmp</tex>, как в решении выше. Пусть, мы рассматриваем <tex>i</tex>-й в лексикографическом порядке суффикс (т.е. и <tex>i</tex>-й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если <tex>tmp[sa[i - 1] + 1] < tmp[sa[i] + 1]</tex>, т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.
 +
 
 +
==== Пример ====
 +
Дан суффиксный массив <tex>[7, 5, 1, 3, 6, 2, 4]</tex>.
 +
Цветами показаны места, после которых добавляются новые символы.
 +
 
 +
[[Файл:ExampleSuffixArray.png|center]]
  
=== Псевдокод ===
+
==== Псевдокод ====
  '''string''' ('''int[]''' sa):
+
  '''string''' fromSuffixArrayToString('''int[]''' sa):
 
   '''for''' i = 1 '''to''' n
 
   '''for''' i = 1 '''to''' n
 
         tmp[sa[i]] = alphabet[i]
 
         tmp[sa[i]] = alphabet[i]
 
   cur = 1
 
   cur = 1
   s[1] = alphabet[1]
+
   s[sa[1]] = alphabet[1]
 
   '''for''' i = 2 '''to''' n
 
   '''for''' i = 2 '''to''' n
 
         j = sa[i - 1]
 
         j = sa[i - 1]
 
         k = sa[i]
 
         k = sa[i]
 
         '''if''' tmp[j + 1] > tmp[k + 1]  
 
         '''if''' tmp[j + 1] > tmp[k + 1]  
             cur++;
+
             cur++
         s[i] = alphabet[cur]       
+
         s[sa[i]] = alphabet[cur]       
 
   '''return''' s
 
   '''return''' s
 +
 +
==== Доказательство минимальности ====
 +
Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.
  
 
== Применения ==
 
== Применения ==
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + \log(|s|))</tex>.
+
 
* Позволяет вычислить наибольший общий префикс (англ. ''longest common prefix'', ''LCP'') для всех соседних в лексикографическом порядке суффиксов строки <tex>s</tex> за <tex>O(|s|)</tex>, то есть построить массив <tex>LCP[1 .. |s| - 1]</tex>, где <tex>LCP[i]</tex> {{---}} длина наибольшего общего префикса суффиксов <tex>s[suf[i] .. |s|]</tex> и <tex>s[suf[i + 1] .. |s|]</tex>.
+
=== Поиск подстроки в строке ===
* Позволяет найти количество различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти.
+
 
* Позволяет найти наименьший циклический сдвиг строки за время <tex>O(|s| \log(|s|))</tex>.
+
{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}
* Позволяет найти максимальную по длине строку, ветвящуюся влево и вправо за время <tex>SA + O(n)</tex>, где <tex>SA</tex> {{---}} время построения суффиксного массива.
+
 
 +
=== Подсчёт LCP для лексикографически соседних суффиксов ===
 +
 
 +
{{main|Алгоритм Касаи и др.}}
 +
 
 +
=== Число различных подстрок в строке ===
 +
 
 +
Вычисление числа различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти с использованием [[Алгоритм_Касаи_и_др.|LCP]]<ref name="ref1">[http://e-maxx.ru/algo/suffix_array#8 MAXimal :: algo :: Суффиксный массив :: Количество различных подстрок]</ref>.
 +
 
 +
=== Максимальная по длине ветвящаяся влево и вправо строка ===
 +
 
 +
Данная задача также может быть [[Сжатое_суффиксное_дерево#Поиск строки максимальной длины, ветвящейся влево и вправо|решена]] при помощи [[Сжатое_суффиксное_дерево|суффиксного дерева]].
 +
 
 +
=== Самая длинная строка p, входящая в t дважды и не пересекаясь ===
 +
 
 +
{{Задача
 +
|definition=
 +
Поиск самой длинной строки <tex>p</tex>, входящей в строку <tex>t</tex> дважды и не пересекаясь.}}
 +
==== Основные положения ====
 +
Построим суффиксный массив строки <tex>t</tex> и посчитаем на нем [[Алгоритм_Касаи_и_др.|LCP]].
 +
Для суффикса <tex>s</tex> символом <tex>s'</tex> будем обозначать индекс этого суффикса в суффиксном массиве.
 +
 
 +
Рассмотрим какие-нибудь суффиксы <tex>i</tex> и <tex>j</tex> строки <tex>t</tex> такие, что <tex>i' \leqslant j'</tex>.
 +
Будем говорить, что строка <tex>s</tex> соответствует каким-нибудь суффиксам <tex>i</tex> и <tex>j</tex>, если она равна максимальному префиксу этих суффиксов.
 +
Будем говорить, что суффиксы <tex>i</tex> и <tex>j</tex> соответствуют строке <tex>s</tex>, если <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, а суффиксы <tex>i</tex> и <tex>j</tex> соответствуют позициям этих вхождений.
 +
 
 +
Для произвольной строки <tex>s</tex> и двух суффиксов, соответствующих ей, введем два условия:
 +
# <tex>\max(|i|, |j|) \geqslant \min(|i|, |j|) + |s|</tex>
 +
# <tex>|s| = \min\limits_{k=i'\dots j'}lcp[k]</tex>
 +
 
 +
{{Утверждение
 +
|statement=
 +
Строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условию 1.
 +
|proof=
 +
'''Необходимое условие:'''
 +
 
 +
Если строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то один из суффиксов <tex>i</tex> и <tex>j</tex> хотя бы на <tex>|s|</tex> длиннее другого. Т.е. условие 1 выполнено.
 +
 
 +
'''Достаточное условие:'''
 +
 
 +
Из того, что выполняется условие 1 следует, что один из суффиксов хотя бы на <tex>|s|</tex> длиннее другого. При этом они оба начинаются со строки <tex>s</tex>. Поэтому строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь.
 +
}}
 +
 
 +
 
 +
{{Утверждение
 +
|statement=
 +
Если строка <tex>s</tex> является максимальной входящей в <tex>t</tex> дважды, то она удовлетворяет условию 2.
 +
|proof=
 +
Пусть это не так и <tex>|s| < \min\limits_{k=i'\dots j'}lcp[k]</tex> (больше она быть не может). Тогда получим, что <tex>|s|</tex> меньше, чем длина наибольшего общего префикса суффиксов <tex>i</tex> и <tex>j</tex>, чего быть не может по построению <tex>i</tex> и <tex>j</tex>.
 +
}}
 +
 
 +
==== Наивный алгоритм ====
 +
# Построим суффиксный массив, посчитаем на нём [[Алгоритм_Касаи_и_др.|LCP]].
 +
# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
 +
 
 +
Этот алгоритм можно реализовать за <tex>O(n^3 + \mathrm{SA})</tex> или за <tex>O(n^2 + \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
 +
 
 +
==== Оптимальное решение ====
 +
===== Идея =====
 +
Будем перебирать всевозможные подстроки <tex>s</tex> строки <tex>t</tex> такие, что они входят в <tex>t</tex> дважды и удовлетворяют условию 2 при любых <tex>i</tex> и <tex>j</tex>, где <tex>i</tex> и <tex>j</tex> {{---}} суффиксы, соответствующие двум любым вхождениям <tex>s</tex> в <tex>t</tex> (т.е. не обязательно непересекающимся). Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1.
 +
Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
 +
 
 +
Заметим теперь, что искомые строки <tex>s</tex> {{---}} это префиксы суффиксов <tex>k</tex> длины <tex>lcp[k]</tex>.
 +
Для того, чтобы найти для каждой такой строки <tex>s</tex> суффиксы <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1, воспользуемся [[Стек|стеком]].
 +
 
 +
===== Алгоритм =====
 +
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>k</tex> длины <tex>lcp[k']</tex> (т.е. строки <tex>s</tex>) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>i</tex> и максимальный по длине <tex>j</tex>. Обозначим за <tex>st</tex> вершину стека, а за <tex>s</tex> {{---}} текущий рассматриваемый суффикс.
 +
# Возможны три случая:
 +
#* <tex>|st| = lcp[s']</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.
 +
#* <tex>|st| \geqslant lcp[s']</tex><br>В этом случае добавляем новую вершину в стек и обновляем для неё <tex>i</tex> и <tex>j</tex>.
 +
#* <tex>|st| \leqslant lcp[s']</tex><br>Достаем вершину из стека и ''пробрасываем'' значения <tex>i</tex> и <tex>j</tex> из неё в новую вершину стека. Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
 +
# Если в какой-то момент <tex>i</tex> и <tex>j</tex> станут удовлетворять условию 1, обновляем ответ.
 +
 
 +
===== Оценка времени работы =====
 +
Т.к. подсчёт <tex>lcp</tex> выполняется за <tex>O(n)</tex>, и для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n + \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
  
 
==См. также==
 
==См. также==
Строка 51: Строка 138:
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
 
* [[Алгоритм Касаи и др.]]
 
* [[Алгоритм Касаи и др.]]
 +
 +
==Примечания==
 +
<references/>
  
 
== Источники ==
 
== Источники ==

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

Определение:
Cуффиксным массивом (англ. suffix array) строки [math]s[1 .. n][/math] называется массив [math]suf[/math] целых чисел от [math]1[/math] до [math]n[/math], такой, что суффикс [math]s[suf[i]..n][/math][math]i[/math]-й в лексикографическом порядке среди всех непустых суффиксов строки [math]s[/math].


Пример

[math]s = abacaba[/math]

SuffixArray.png

Значит, суффиксный массив для строки [math]s[/math] равен [math][7, 5, 1, 3, 6, 2, 4][/math].

Восстановление строки по суффиксному массиву

Задача:
Дан суффиксный массив некоторой строки [math]s[/math], необходимо восстановить строку за время [math]O(|s|)[/math].


Вариант для бесконечного алфавита

Так как наш алфавит не ограничен, можно [math]i[/math]-й в лексикографическом порядке суффикс сопоставить с [math]i[/math]-й буквой в алфавите.

Доказательство корректности

Если отсортировать суффиксы, то первые буквы будут расположены в том же порядке, как и в алфавите.

Псевдокод

string fromSuffixArrayToString(int[] sa):
  for i = 1 to n
       s[sa[i]] = alphabet[i] 
  return s

Вариант для минимально возможного

Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку [math]tmp[/math], как в решении выше. Пусть, мы рассматриваем [math]i[/math]-й в лексикографическом порядке суффикс (т.е. и [math]i[/math]-й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если [math]tmp[sa[i - 1] + 1] \lt tmp[sa[i] + 1][/math], т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.

Пример

Дан суффиксный массив [math][7, 5, 1, 3, 6, 2, 4][/math]. Цветами показаны места, после которых добавляются новые символы.

ExampleSuffixArray.png

Псевдокод

string fromSuffixArrayToString(int[] sa):
  for i = 1 to n
       tmp[sa[i]] = alphabet[i]
  cur = 1
  s[sa[1]] = alphabet[1]
  for i = 2 to n
       j = sa[i - 1]
       k = sa[i]
       if tmp[j + 1] > tmp[k + 1] 
           cur++
       s[sa[i]] = alphabet[cur]       
  return s

Доказательство минимальности

Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.

Применения

Поиск подстроки в строке

Подсчёт LCP для лексикографически соседних суффиксов

Основная статья: Алгоритм Касаи и др.

Число различных подстрок в строке

Вычисление числа различных подстрок в строке за время [math]O(|s| \log(|s|))[/math] и [math]O(|s|)[/math] дополнительной памяти с использованием LCP[1].

Максимальная по длине ветвящаяся влево и вправо строка

Данная задача также может быть решена при помощи суффиксного дерева.

Самая длинная строка p, входящая в t дважды и не пересекаясь

Задача:
Поиск самой длинной строки [math]p[/math], входящей в строку [math]t[/math] дважды и не пересекаясь.

Основные положения

Построим суффиксный массив строки [math]t[/math] и посчитаем на нем LCP. Для суффикса [math]s[/math] символом [math]s'[/math] будем обозначать индекс этого суффикса в суффиксном массиве.

Рассмотрим какие-нибудь суффиксы [math]i[/math] и [math]j[/math] строки [math]t[/math] такие, что [math]i' \leqslant j'[/math]. Будем говорить, что строка [math]s[/math] соответствует каким-нибудь суффиксам [math]i[/math] и [math]j[/math], если она равна максимальному префиксу этих суффиксов. Будем говорить, что суффиксы [math]i[/math] и [math]j[/math] соответствуют строке [math]s[/math], если [math]s[/math] входит в [math]t[/math] дважды и не пересекаясь, а суффиксы [math]i[/math] и [math]j[/math] соответствуют позициям этих вхождений.

Для произвольной строки [math]s[/math] и двух суффиксов, соответствующих ей, введем два условия:

  1. [math]\max(|i|, |j|) \geqslant \min(|i|, |j|) + |s|[/math]
  2. [math]|s| = \min\limits_{k=i'\dots j'}lcp[k][/math]
Утверждение:
Строка [math]s[/math] входит в [math]t[/math] дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условию 1.
[math]\triangleright[/math]

Необходимое условие:

Если строка [math]s[/math] входит в [math]t[/math] дважды и не пересекаясь, то один из суффиксов [math]i[/math] и [math]j[/math] хотя бы на [math]|s|[/math] длиннее другого. Т.е. условие 1 выполнено.

Достаточное условие:

Из того, что выполняется условие 1 следует, что один из суффиксов хотя бы на [math]|s|[/math] длиннее другого. При этом они оба начинаются со строки [math]s[/math]. Поэтому строка [math]s[/math] входит в [math]t[/math] дважды и не пересекаясь.
[math]\triangleleft[/math]


Утверждение:
Если строка [math]s[/math] является максимальной входящей в [math]t[/math] дважды, то она удовлетворяет условию 2.
[math]\triangleright[/math]
Пусть это не так и [math]|s| \lt \min\limits_{k=i'\dots j'}lcp[k][/math] (больше она быть не может). Тогда получим, что [math]|s|[/math] меньше, чем длина наибольшего общего префикса суффиксов [math]i[/math] и [math]j[/math], чего быть не может по построению [math]i[/math] и [math]j[/math].
[math]\triangleleft[/math]

Наивный алгоритм

  1. Построим суффиксный массив, посчитаем на нём LCP.
  2. Переберем все пары [math]i[/math] и [math]j[/math] такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.

Этот алгоритм можно реализовать за [math]O(n^3 + \mathrm{SA})[/math] или за [math]O(n^2 + \mathrm{SA})[/math], где [math]\mathrm{SA}[/math] — время построения суффиксного массива.

Оптимальное решение

Идея

Будем перебирать всевозможные подстроки [math]s[/math] строки [math]t[/math] такие, что они входят в [math]t[/math] дважды и удовлетворяют условию 2 при любых [math]i[/math] и [math]j[/math], где [math]i[/math] и [math]j[/math] — суффиксы, соответствующие двум любым вхождениям [math]s[/math] в [math]t[/math] (т.е. не обязательно непересекающимся). Для каждой такой строки [math]s[/math] попробуем найти [math]i[/math] и [math]j[/math], удовлетворяющие условию 1. Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.

Заметим теперь, что искомые строки [math]s[/math] — это префиксы суффиксов [math]k[/math] длины [math]lcp[k][/math]. Для того, чтобы найти для каждой такой строки [math]s[/math] суффиксы [math]i[/math] и [math]j[/math], удовлетворяющие условию 1, воспользуемся стеком.

Алгоритм
  1. Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов [math]k[/math] длины [math]lcp[k'][/math] (т.е. строки [math]s[/math]) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс [math]i[/math] и максимальный по длине [math]j[/math]. Обозначим за [math]st[/math] вершину стека, а за [math]s[/math] — текущий рассматриваемый суффикс.
  2. Возможны три случая:
    • [math]|st| = lcp[s'][/math]
      Тогда просто обновляем [math]i[/math] и [math]j[/math] для вершины стека.
    • [math]|st| \geqslant lcp[s'][/math]
      В этом случае добавляем новую вершину в стек и обновляем для неё [math]i[/math] и [math]j[/math].
    • [math]|st| \leqslant lcp[s'][/math]
      Достаем вершину из стека и пробрасываем значения [math]i[/math] и [math]j[/math] из неё в новую вершину стека. Это нужно для того, чтобы не потерять значения [math]i[/math] и [math]j[/math], которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
  3. Если в какой-то момент [math]i[/math] и [math]j[/math] станут удовлетворять условию 1, обновляем ответ.
Оценка времени работы

Т.к. подсчёт [math]lcp[/math] выполняется за [math]O(n)[/math], и для каждого суффикса мы выполняем [math]O(1)[/math] операций, то итоговое время работы [math]O(n + \mathrm{SA})[/math], где [math]\mathrm{SA}[/math] — время построения суффиксного массива.

См. также

Примечания

Источники