Изменения

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

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

6 байт добавлено, 17:15, 5 июня 2016
м
Идея
==== Оптимальное решение ====
===== Идея =====
Чтобы достигнуть асимптотики <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> {{- --}} суффиксы, соответствующие двум любым вхождениям 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, воспользуемся стеком
165
правок

Навигация