Изменения

Перейти к: навигация, поиск

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

988 байт добавлено, 1 апрель
Псевдокод: записываем в строку 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>.}}
== Пример ==
tmp[sa[i]] = alphabet[i]
cur = 1
s[sa[1]] = alphabet[1]
'''for''' i = 2 '''to''' n
j = sa[i - 1]
'''if''' tmp[j + 1] > tmp[k + 1]
cur++
s[sa[i]] = alphabet[cur]
'''return''' s
== Применения ==
 
Здесь и далее <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
=== Поиск подстроки в строке ===
{{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>.
=== Максимальная по длине ветвящаяся влево и вправо строка ===
{{Задача
|definition=
Поиск самой длинной строки <tex>p</tex>, входящей в строку <tex>t</tex> дважды и не пересекаясь за <tex>\mathrm{SA} + O(n).</tex>}} 
==== Основные положения ====
Построим суффиксный массив строки <tex>t</tex> и посчитаем на нем [[Алгоритм_Касаи_и_др.|LCP]].
Рассмотрим какие-нибудь суффиксы Для суффикса <tex>is</tex> и символом <tex>js'</tex> строки будем обозначать индекс этого суффикса в суффиксном массиве. Рассмотрим какие-нибудь суффиксы <tex>ti</tex>. Обозначим их позиции в суффиксном массиве за и <tex>i'j</tex> и строки <tex>j't</tex>такие, причем что <tex>i' \leq 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(len(|i')|, len(|j')|) \geq geqslant \min(len(|i')|, len(|j')|) + |s|</tex># <tex>|s| = \min_min\limits_{k={i'}\dots{j'}}(lcp_k)lcp[k]</tex> 
{{Утверждение
|author=
|statement=
Если для каких-нибудь суффиксов <tex>i</tex> и <tex>j</tex> соответствующая им строка Строка <tex>s</tex> удовлетворяет условиям 1 и 2, то она входит в <tex>t</tex> дважды и не пересекаясьтогда и только тогда, когда она удовлетворяет условию 1.
|proof=
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> дважды и не пересекаясь.
}}
 
{{Утверждение
|author=
|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> удовлетворяют условиям 1 , чего быть не может по построению <tex>i</tex> и 2<tex>j</tex>.|proof= proof
}}
 
 
Т.о. строка входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условиям 1 и 2.
==== Наивный алгоритм ====
# Переберем все пары <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>O(n)</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_klcp[k]</tex>. Для того, чтобы найти для каждой такой строки <tex>s</tex> суффиксы <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1, воспользуемся [[Стек|стеком]].
===== Алгоритм =====
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>k</tex> длины <tex>lcp_klcp[k']</tex> (т.е. строки <tex>s</tex>) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>i</tex> и максимальный по длине <tex>j</tex>. Обозначим за <tex>st</tex> вершину стека, а за <tex>s</tex> {{---}} текущий рассматриваемый суффикс.
# Возможны три случая:
## * <tex>lcp_{|st} | = lcp_slcp[s']</tex>. <br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека: '''if''' (<tex>len_i > len_s</tex>) '''then''' <tex>i = s</tex>;.## * <tex>lcp_{|st} | \geq lcp_sgeqslant lcp[s']</tex>. Тогда <br>В этом случае добавляем новую вершину в стек и обновляем для нее неё <tex>i</tex> и <tex>j</tex>: <tex>i = j = s;</tex>.## * <tex>lcp_{|st} | \leq lcp_sleqslant lcp[s']</tex>. <br>Достаем вершину из стека и "''пробрасываем" '' значения <tex>i</tex> и <tex>j</tex> из нее неё в новую вершину стека. Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.# Если в какой-то момент <tex>i</tex> и <tex>j</tex> станут удовлетворять условию 1, обновляем ответ: '''if''' (<tex>len_s > len_{ans}</tex>) '''then''' <tex>s = ans</tex>;.
===== Оценка времени работы =====
Т.к. подсчёт <tex>lcp</tex> выполняется за <tex>O(n)</tex>, и для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n+ \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
==См. также==
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
* [[Алгоритм Касаи и др.]]
 
==Примечания==
<references/>
== Источники ==
Анонимный участник

Навигация