Изменения

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

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

2 байта добавлено, 19:02, 5 июня 2016
Алгоритм
===== Алгоритм =====
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <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[s']</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.
165
правок

Навигация