165
правок
Изменения
м
→Алгоритм
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <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>. <br>Тогда просто обновляем <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>. <br>Тогда добавляем новую вершину в стек и обновляем для нее <tex>i</tex> и <tex>j</tex>: <tex>i = j = s;</tex>.## * <tex>lcp_{st} \leq lcp_s</tex>. <br>Достаем вершину из стека и "пробрасываем" значения <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>;.
===== Оценка времени работы =====
