Изменения

'''<tex>i</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>.}} = = Пример ==<tex>s = abacaba</tex> [[Файл:SuffixArray.png|500px]] Значит, суффиксный массив для строки <tex>s</tex> равен <tex>[7, 5, 1 , 3, 6, 2, 4]</tex>.. n == Восстановление строки по суффиксному массиву =={{Задача|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 дважды и не пересекаясь === {{Задача

'''Cуффиксным массивом''' Поиск самой длинной строки <tex>s[1 .. n]p</tex> называется массив , входящей в строку <tex>suft</tex> целых чисел от дважды и не пересекаясь.}}==== Основные положения ====Построим суффиксный массив строки <tex>1t</tex> до и посчитаем на нем [[Алгоритм_Касаи_и_др.|LCP]].Для суффикса <tex>ns</tex>, такой, что суффикс под номером символом <tex>s[suf[i]</tex> <tex>i'</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 = abacaba</tex>входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условию 1. Суффиксы |proof= '''Необходимое условие:''' Если строка <tex>s</tex> входит в лексикографическом порядке:<brtex>t</tex> дважды и не пересекаясь, то один из суффиксов <tex>i</tex> и <tex>j</tex> хотя бы на <tex>|s|</tex>длиннее другого. Т.е. условие 1 выполнено. '''Достаточное условие:''' Из того, что выполняется условие 1) следует, что один из суффиксов хотя бы на <tex>a|s|</tex>длиннее другого. При этом они оба начинаются со строки <tex>s<br/tex>2) . Поэтому строка <tex>abas</tex>входит в <tex>t<br/tex>дважды и не пересекаясь.}}  {{Утверждение|statement=3) Если строка <tex>abacabas</tex>является максимальной входящей в <tex>t<br/tex>дважды, то она удовлетворяет условию 2.|proof=4Пусть это не так и <tex>|s| < \min\limits_{k=i'\dots j'}lcp[k]</tex> (больше она быть не может) . Тогда получим, что <tex>|s|</tex> меньше, чем длина наибольшего общего префикса суффиксов <tex>acabai</tex>и <tex>j<br/tex>5) , чего быть не может по построению <tex>bai</tex>и <tex>j<br/tex>.}} ==== Наивный алгоритм ====# Построим суффиксный массив, посчитаем на нём [[Алгоритм_Касаи_и_др.|LCP]].6) # Переберем все пары <tex>bacabai</tex>и <tex>j<br/tex>такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки. 7Этот алгоритм можно реализовать за <tex>O(n^3 + \mathrm{SA}) </tex> или за <tex>cabaO(n^2 + \mathrm{SA})</tex>, где <tex>\mathrm{SA}<br/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>(7т.е. не обязательно непересекающимся). Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1. Таким образом, 5мы рассмотрим все строки, соответствующие условиям 1и 2, и, 3следовательно, 6найдем ответ. Алгоритм корректный. Заметим теперь, 2что искомые строки <tex>s</tex> {{---}} это префиксы суффиксов <tex>k</tex> длины <tex>lcp[k]</tex>. Для того, 4)чтобы найти для каждой такой строки <tex>s</tex> суффиксы <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1, воспользуемся [[Стек|стеком]].

== Применения === Алгоритм =====* Позволяет найти все вхождения образца # Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>pk</tex> в строку длины <tex>slcp[k']</tex> за время (т.е. строки <tex>O(|p| + \log(|s|)</tex>)в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>i</tex>* Позволяет вычислить и максимальный по длине <tex>lcpj</tex> (longest common prefix) для всех соседних в лексикографическом порядке суффиксов строки . Обозначим за <tex>sst</tex> вершину стека, а за <tex>O(|s|)</tex>, то есть построить массив {{---}} текущий рассматриваемый суффикс.# Возможны три случая:#* <tex>|st| = lcp[1 .. |s| - 1']</tex>, где <br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.#* <tex>|st| \geqslant lcp[is']</tex> {{---}} длина наибольшего общего префикса суффиксов <br>В этом случае добавляем новую вершину в стек и обновляем для неё <tex>s[suf[i] .</tex> и <tex>j</tex>. #* <tex>|st|\leqslant lcp[s|']</tex> <br>Достаем вершину из стека и ''пробрасываем'' значения <tex>s[suf[i + 1] </tex> и <tex>j</tex> из неё в новую вершину стека.Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины. |s|]# Если в какой-то момент <tex>i</tex> и <tex>j</tex>станут удовлетворять условию 1, обновляем ответ.

==Литература=== Оценка времени работы =====* Гасфилд ДТ. Строкик. подсчёт <tex>lcp</tex> выполняется за <tex>O(n)</tex>, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n + \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---е изд}} время построения суффиксного массива.