Изменения

'''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>.}}

===Поиск подстроки в строке === {{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 дважды и не пересекаясь === {{ОпределениеЗадача

'''Строка Поиск самой длинной строки <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>. ''right branching string'')Будем говорить, что строка <tex>s</tex> соответствует каким-нибудь суффиксам <tex>i</tex> и <tex>j</tex>, если существуют символы она равна максимальному префиксу этих суффиксов.Будем говорить, что суффиксы <tex>ci</tex> и <tex>dj</tex> соответствуют строке <tex>s</tex>, такие что если <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, а суффиксы <tex>ci</tex> и <tex>\nej</tex> соответствуют позициям этих вхождений. Для произвольной строки <tex>ds</tex> и двух суффиксов, соответствующих ей, введем два условия: # <tex>sc\max(|i|, |j|) \geqslant \min(|i|, |j|) + |s|</tex> и # <tex>sd|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 выполнено.  '''Достаточное условие:'left branching'') Из того, что выполняется условие 1 следует, если что один из суффиксов хотя бы на <tex>|s|</tex> длиннее другого. При этом они оба начинаются со строки <tex>css</tex> и . Поэтому строка <tex>dss</tex> {{---}} подстроки входит в <tex>t</tex>дважды и не пересекаясь.

  {{ОпределениеУтверждение|statement=Если строка <tex>s</tex> является максимальной входящей в <tex>t</tex> дважды, то она удовлетворяет условию 2.|definitionproof=Пусть это не так и <tex>|s| < \min\limits_{k=i'\dots j''Левый символ''' для позиции }lcp[k]</tex> (больше она быть не может). Тогда получим, что <tex>|s|</tex> меньше, чем длина наибольшего общего префикса суффиксов <tex>i</tex> строки и <tex>Sj</tex> {{---}} это символ , чего быть не может по построению <tex>S(i-1)</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>aabcabd\mathrm{SA}</tex> :{{---}} время построения суффиксного массива. {| class="wikitable" border = 1== Оптимальное решение ====|-!Суффиксный массив|- style = "text-align = right"=== Идея =====| 1 |Будем перебирать всевозможные подстроки <tex>s</tex> строки <tex>t</tex> такие, что они входят в <tex>abcabdt</tex>|-| дважды и удовлетворяют условию 2 |при любых <tex>i</tex> и <tex>j</tex>, где <tex>i</tex> и <tex>abdj</tex>|{{---| 3 |}} суффиксы, соответствующие двум любым вхождениям <tex>s</tex> в <tex>t</tex> (т.е. не обязательно непересекающимся). Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>bcabdj</tex>, удовлетворяющие условию 1. Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.|-| 4 |Заметим теперь, что искомые строки <tex>bds</tex>|{{---}} это префиксы суффиксов <tex>k</tex> длины <tex>lcp[k]</tex>. | 5 |Для того, чтобы найти для каждой такой строки <tex>s</tex> суффиксы <tex>cabdi</tex>|-| 6 |и <tex>dj</tex>, удовлетворяющие условию 1, воспользуемся [[Стек|}стеком]].

Далее вычисляется <tex>LCP</tex> для суффиксного массива, и находятся левые символы суффиксов:{| class="wikitable" border = 1|-!Левый символ!Суффиксный массив!LCP|- style = "text-align = center"= Алгоритм =====| 1 |# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>ak</tex>||длины <tex>abcabdlcp[k']</tex>||(т.е. строки <tex>\#s</tex>|-| 2 |) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>ci</tex>||и максимальный по длине <tex>abdj</tex>||. Обозначим за <tex>2st</tex>|-| 3 |вершину стека, а за <tex>a</tex>||<tex>bcabd</tex>||<tex>0s</tex>{{---}} текущий рассматриваемый суффикс.|-# Возможны три случая:| 4 |<tex>a#* </tex>|st|<tex>bd</tex>||<tex>1= lcp[s']</tex>|-| 5 |<texbr>bТогда просто обновляем </tex>||<tex>cabdi</tex>||и <tex>0j</tex>для вершины стека.|-| 6 |<tex>b#* </tex>|st|\geqslant lcp[s']</tex>d</texbr>||В этом случае добавляем новую вершину в стек и обновляем для неё <tex>0i</tex>|}Максимальная строка, ветвящаяся влево и вправо, находится путём проверки значений <tex>LCPj</tex> и левого символа:Ветвление вправо:.#*Если <tex>LCP|st| \leqslant lcp[s']</tex> от пары суффиксов <tex>s_1</texbr> Достаем вершину из стека и ''пробрасываем'' значения <tex>s_2i</tex> больше нуля и не равен длинам этих суффиксов, то строка <tex>sj</tex>, равная <tex>s_1[1из неё в новую вершину стека..LCP(s_1Это нужно для того,s_2)]</tex>, ветвится вправо. Ветвление влево:*Если левые символы чтобы не потерять значения <tex>s_1i</tex> и <tex>s_2j</tex> не равны, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.# Если в какой-то строка момент <tex>si</tex>, равная и <tex>s_1[1..LCP(s_1,s_2)]j</tex>станут удовлетворять условию 1, ветвится влевообновляем ответ.

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