Изменения

* Позволяет найти все вхождения Здесь и далее <tex>SA</tex> {{---}} время построения суффиксного массива. === Поиск подстроки в строке === Поиск всех вхождений образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + \log(|s|))</tex>.* Позволяет вычислить наибольший общий префикс (англ[[Алгоритм_поиска_подстроки_в_строке_с_помощью_суффиксного_массива|Основная статья]] === Подсчет LCP соседних лексикографически суффиксов === Подсчет [[Алгоритм_Касаи_и_др. ''longest common prefix'', ''|LCP'') ]] для всех соседних в лексикографическом порядке суффиксов строки <tex>s</tex> за <tex>O(|s|)</tex>, то есть построить массив построение массива <tex>LCP[1 .. |s| - 1]</tex>, где <tex>LCP[i]</tex> {{---}} длина наибольшего общего префикса суффиксов <tex>s[suf[i] .. |s|]</tex> и <tex>s[suf[i + 1] .. |s|]</tex>.* Позволяет найти количество === Количество различных подстрок в строке === Вычисление количества различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти.* Позволяет найти наименьший === Наименьший циклический сдвиг строки === Поиск наименьшего циклического сдвига строки за время <tex>O(|s| \log(|s|))</tex>.* Позволяет найти максимальную [[Декомпозиция_Линдона#Поиск лексикографически минимального суффикса строки|Основная статья]] === Максимальная по длине ветвящаяся влево и вправо строка === Поиск максимальной по длине строкустроки, ветвящуюся ветвящейся влево и вправо за время <tex>SA + O(n)</tex>. === Самая длинная строка <tex>p</tex>, входящая в <tex>t</tex> дважды и не пересекаясь === Поиск самой длинной строки <tex>p</tex>, входящей в строку <tex>t</tex> дважды и не пересекаясь за <tex>SA + O(n)</tex> '''Решение:'''Построим суфмас строки <tex>t</tex> и посчитаем на нем LCP алгоритмом [[Алгоритм_Касаи_и_др.|Касаи, Аримуры, Арикавы, Ли, Парка]].Рассмотрим какие-нибудь суффиксы <tex>i</tex> и <tex>j</tex> строки <tex>t</tex>. Обозначим их позиции в суфмасе за <tex>i'</tex> и <tex>j'</tex>, причем <tex>i' \leq 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>max(len(i'), len(j')) \geq min(len(i'), len(j')) + |s|</tex># <tex>|s| = \min_{k={i'}\dots{j'}}(lcp_k)</tex>  {{Утверждение|author=|statement=Если для каких-нибудь суффиксов <tex>i</tex> и <tex>j</tex> соответствующая им строка <tex>s</tex> удовлетворяет условиям 1 и 2, то она входит в <tex>t</tex> дважды и не пересекаясь.|proof= proof}} {{Утверждение|author=|statement=Если строка <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, то соответствующие ей суффиксы <tex>i</tex> и <tex>j</tex> удовлетворяют условиям 1 и 2.|proof= proof}}  Т.о. строка входит в <tex>t</tex> дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условиям 1 и 2.  Тогда на ум приходит следующий наивный алгоритм:# Построим суффиксный массив, посчитаем на нём LCP.# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки. Этот алгоритм можно реализовать за <tex>O(n^3)</tex> или, если немного подумать, то и за <tex>O(n^2)</tex>. Однако, он не позволяет достигнуть нужной нам асимптотики.  Чтобы достигнуть асимптотики <tex>O(n)</tex>, будем перебирать всевозможные подстроки <tex>s</tex> строки <tex>t</tex>, такие, что они входят в <tex>t</tex> дважды и являются максимальными в том смысле, что <tex>s</tex> удовлетворяет условию 2 при любых <tex>i</tex> и <tex>j</tex>, где <tex>SAi</tex> и <tex>j</tex> - суффиксы, соответствующие двум любым вхождениям s в t (т.е. не обязательно непересекающимся). Для каждой такой строки <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>lcp_{st} = lcp_s</tex>. Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека: '''if''' (<tex>len_i > len_s</tex>) '''then''' <tex>i = s</tex>;## <tex>lcp_{st} \geq lcp_s</tex>. Тогда добавляем новую вершину в стек и обновляем для нее <tex>i</tex> и <tex>j</tex>: <tex>i = j = s;</tex>## <tex>lcp_{st} \leq lcp_s</tex>. Достаем вершину из стека и "пробрасываем" значения <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>O(1)</tex> операций, то итоговое время построения суффиксного массива.работы <tex>O(n)</tex>