Суффиксный массив

2019-04-01T09:36:29Z

37.146.229.100: /* Псевдокод */ записываем в строку s по индексу sa[i], а не по i

{{Определение
|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>.}}

== Пример ==
<tex>s = abacaba</tex>

[[Файл:SuffixArray.png|500px]]

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

== Восстановление строки по суффиксному массиву ==
{{Задача
|definition = Дан суффиксный массив некоторой строки <tex>s</tex>, необходимо восстановить строку за время <tex>O(|s|)</tex>.
}}

=== Вариант для бесконечного алфавита ===
Так как наш алфавит не ограничен, можно <tex>i</tex>-й в лексикографическом порядке суффикс сопоставить с <tex>i</tex>-й буквой в алфавите.

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

==== Псевдокод ====
'''string''' fromSuffixArrayToString('''int[]''' sa):
'''for''' i = 1 '''to''' n
s[sa[i]] = alphabet[i]
'''return''' s

=== Вариант для минимально возможного ===
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <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''' 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

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

== Применения ==

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

{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}

=== Подсчёт 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> {{---}} время построения суффиксного массива.

==См. также==
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
* [[Алгоритм Касаи и др.]]

==Примечания==
<references/>

== Источники ==
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
* [http://ru.wikipedia.org/wiki/Суффиксный_массив Википедия — Суффиксный массив]
* [http://en.wikipedia.org/wiki/Suffix_array Wikipedia — Suffix array]
* [http://habrahabr.ru/post/115346/ Habrahabr — Суффиксный массив — удобная замена суффиксного дерева]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Суффиксный массив]]

Викиконспекты - Вклад участника [ru]

Суффиксный массив