Изменения

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

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

10 байт добавлено, 17:33, 5 июня 2016
м
Алгоритм
# Возможны три случая:
#* <tex>lcp_{st} = lcp_s</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.
#* <tex>lcp_{st} \geq geqslant lcp_s</tex><br>Тогда добавляем новую вершину в стек и обновляем для нее <tex>i</tex> и <tex>j</tex>.#* <tex>lcp_{st} \leq leqslant lcp_s</tex><br>Достаем вершину из стека и "пробрасываем" значения <tex>i</tex> и <tex>j</tex> из нее в новую вершину стека. Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
# Если в какой-то момент <tex>i</tex> и <tex>j</tex> станут удовлетворять условию 1, обновляем ответ.
165
правок

Навигация