Изменения

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

s[sa[1]] = alphabet[1]

s[sa[i]] = alphabet[cur]

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

Вычисление числа различных подстрок в строке за время <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>.

Поиск самой длинной строки <tex>p</tex>, входящей в строку <tex>t</tex> дважды и не пересекаясь.}}

Рассмотрим какие-нибудь суффиксы Для суффикса <tex>is</tex> и символом <tex>js'</tex> строки будем обозначать индекс этого суффикса в суффиксном массиве. Рассмотрим какие-нибудь суффиксы <tex>ti</tex>. Обозначим их позиции в суффиксном массиве за и <tex>i'j</tex> и строки <tex>j't</tex>такие, причем что <tex>i' \leqslant j'</tex>.

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

# <tex>|s| = \min\limits_{k=i'\dots j'}(lcp_k)</tex> Здесь и далее <tex>lcp_k</tex> обозначает значение <tex>lcp</tex> для суффикса <tex>[k]</tex> и суффикса, следующего за ним в суффиксном массиве.

Если для каких-нибудь суффиксов <tex>i</tex> и <tex>j</tex> соответствующая им строка Строка <tex>s</tex> удовлетворяет условиям 1 и 2, то она входит в <tex>t</tex> дважды и не пересекаясьтогда и только тогда, когда она удовлетворяет условию 1.

Если строка <tex>s</tex> входит является максимальной входящей в <tex>t</tex> дважды и не пересекаясь, то соответствующие ей суффиксы <tex>i</tex> и <tex>j</tex> удовлетворяют условиям 1 и она удовлетворяет условию 2.|proof= Если строка Пусть это не так и <tex>|s| </tex> входит в <tex>t\min\limits_{k=i'\dots j'}lcp[k]</tex> дважды и (больше она быть не пересекаясьможет). Тогда получим, то один из суффиксов <tex>i</tex> и <tex>j</tex> хотя бы на что <tex>|s|</tex> длиннее другого. Т.е. условие 1 выполнено. Условие 2 выполняетсяменьше, т.к. иначе наибольший общий префикс чем длина наибольшего общего префикса суффиксов <tex>i</tex> и <tex>j</tex> был бы меньше , чего быть не может по построению <tex>|s|i</tex>, чего не может быть по построению и <tex>sj</tex>. Т.е. условие 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.

Заметим теперь, что искомые строки <tex>s</tex> {{---}} это префиксы суффиксов <tex>k</tex> длины <tex>lcp_klcp[k]</tex>.

# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <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> для вершины стека.#* <tex>lcp_{|st} | \geqslant lcp_slcp[s']</tex><br>В этом случае добавляем новую вершину в стек и обновляем для нее неё <tex>i</tex> и <tex>j</tex>.#* <tex>lcp_{|st} | \leqslant lcp_slcp[s']</tex><br>Достаем вершину из стека и ''пробрасываем'' значения <tex>i</tex> и <tex>j</tex> из нее неё в новую вершину стека. Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.

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