Изменения

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

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

65 байт добавлено, 12:36, 1 апреля 2019
Псевдокод: записываем в строку s по индексу sa[i], а не по i
{{Определение
|definition=
'''Cуффиксным массивом''' (англ. ''suffix array'') строки <tex>s[1 .. n]</tex> называется массив <tex>suf</tex> целых чисел от <tex>1</tex> до <tex>n</tex>, такой, что суффикс <tex>s[suf[i]..n]</tex> — <tex>i</tex>-й в [[Лексикографический_порядок|лексикографическом ]] порядке среди всех непустых суффиксов строки <tex>s</tex>.}}
== Пример ==
tmp[sa[i]] = alphabet[i]
cur = 1
s[sa[1]] = alphabet[1]
'''for''' i = 2 '''to''' n
j = sa[i - 1]
'''if''' tmp[j + 1] > tmp[k + 1]
cur++
s[sa[i]] = alphabet[cur]
'''return''' s
{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}
=== Подсчет Подсчёт LCP для лексикографически соседних суффиксов ===
{{main|Алгоритм Касаи и др.}}
# Возможны три случая:
#* <tex>|st| = lcp[s']</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.
#* <tex>|st| \geqslant lcp[s']</tex><br>В этом случае добавляем новую вершину в стек и обновляем для нее неё <tex>i</tex> и <tex>j</tex>.#* <tex>|st| \leqslant lcp[s']</tex><br>Достаем вершину из стека и ''пробрасываем'' значения <tex>i</tex> и <tex>j</tex> из нее неё в новую вершину стека. Это нужно для того, чтобы не потерять значения <tex>i</tex> и <tex>j</tex>, которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
# Если в какой-то момент <tex>i</tex> и <tex>j</tex> станут удовлетворять условию 1, обновляем ответ.
===== Оценка времени работы =====
Т.к. подсчет подсчёт <tex>lcp</tex> выполняется за <tex>O(n)</tex> , и для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n + \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
==См. также==
Анонимный участник

Навигация