Суффиксный массив
Определение: |
Cуффиксным массивом (англ. suffix array) строки | называется массив целых чисел от до , такой, что суффикс — -й в лексикографическом порядке среди всех непустых суффиксов строки .
Содержание
- 1 Пример
- 2 Восстановление строки по суффиксному массиву
- 3 Применения
- 4 См. также
- 5 Источники
Пример
Значит, суффиксный массив для строки
равен .Восстановление строки по суффиксному массиву
Задача: |
Дан суффиксный массив некоторой строки | , необходимо восстановить строку за время .
Вариант для бесконечного алфавита
Так как наш алфавит не ограничен, можно
-й в лексикографическом порядке суффикс сопоставить с -й буквой в алфавите.Доказательство корректности
Если отсортировать суффиксы, то первые буквы будут расположены в том же порядке, как и в алфавите.
Псевдокод
string fromSuffixArrayToString(int[] sa): for i = 1 to n s[sa[i]] = alphabet[i] return s
Вариант для минимально возможного
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку
, как в решении выше. Пусть, мы рассматриваем -й в лексикографическом порядке суффикс (т.е. и -й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если , т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.Пример
Дан суффиксный массив
. Цветами показаны места, после которых добавляются новые символы.Псевдокод
string fromSuffixArrayToString(int[] sa): for i = 1 to n tmp[sa[i]] = alphabet[i] cur = 1 s[1] = alphabet[1] for i = 2 to n j = sa[i - 1] k = sa[i] if tmp[j + 1] > tmp[k + 1] cur++ s[i] = alphabet[cur] return s
Доказательство минимальности
Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.
Применения
Здесь и далее
— время построения суффиксного массива.Поиск подстроки в строке
Подсчет LCP для лексикографически соседних суффиксов
Число различных подстрок в строке
Вычисление числа различных подстрок в строке за время LCP[1].
и дополнительной памяти с использованиемМаксимальная по длине ветвящаяся влево и вправо строка
Данная задача также может быть решена при помощи суффиксного дерева.
Самая длинная строка p, входящая в t дважды и не пересекаясь
Задача: |
Поиск самой длинной строки | , входящей в строку дважды и не пересекаясь за
Основные положения
Построим суффиксный массив строки LCP. Рассмотрим какие-нибудь суффиксы и строки . Обозначим их позиции в суффиксном массиве за и , причем . Будем говорить, что строка соответствует каким-нибудь суффиксам и , если она равна максимальному префиксу этих суффиксов. Будем говорить, что суффиксы и соответствуют строке , если входит в дважды и не пересекаясь, а суффиксы и соответствуют позициям этих вхождений.
и посчитаем на немВведем два условия:
Здесь и далее
означает длину суффикса , а обозначает значение для суффикса и суффикса, следующего за ним в суффиксном массиве.Утверждение: |
Если для каких-нибудь суффиксов и соответствующая им строка удовлетворяет условиям 1 и 2, то она входит в дважды и не пересекаясь. |
Из того, что выполняется условие 1 следует, что один из суффиксов хотя бы на длиннее другого. При этом они оба начинаются со строки . Поэтому строка входит в дважды и не пересекаясь.Условию 2 же строка удовлетворяет по построению. Ч.т.д. |
Утверждение: |
Если строка входит в дважды и не пересекаясь, то соответствующие ей суффиксы и удовлетворяют условиям 1 и 2. |
Если строка входит в дважды и не пересекаясь, то один из суффиксов и хотя бы на длиннее другого. Т.е. условие 1 выполнено.Условие 2 выполняется, т.к. иначе наибольший общий префикс Ч.т.д. и был бы меньше , чего не может быть по построению . Т.е. условие 2 тоже выполнено. |
Т.о. строка входит в дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условиям 1 и 2.
Наивный алгоритм
- Построим суффиксный массив, посчитаем на нём LCP.
- Переберем все пары и такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
Этот алгоритм можно реализовать за
или за . Однако, он не позволяет достигнуть нужной нам асимптотики.Оптимальное решение
Идея
Чтобы достигнуть асимптотики
, будем перебирать всевозможные подстроки строки такие, что они входят в дважды и удовлетворяют условию 2 при любых и , где и — суффиксы, соответствующие двум любым вхождениям в (т.е. не обязательно непересекающимся).Для каждой такой строки попробуем найти и , удовлетворяющие условию 1. Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.Заметим теперь, что искомые строки стеком.
— это префиксы суффиксов длины . Для того, чтобы найти для каждой такой строки суффиксы и , удовлетворяющие условию 1, воспользуемсяАлгоритм
- Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов длины (т.е. строки ) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс и максимальный по длине . Обозначим за вершину стека, а за — текущий рассматриваемый суффикс.
- Возможны три случая:
-
Тогда просто обновляем и для вершины стека. -
Тогда добавляем новую вершину в стек и обновляем для нее и . -
Достаем вершину из стека и "пробрасываем" значения и из нее в новую вершину стека. Это нужно для того, чтобы не потерять значения и , которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
-
- Если в какой-то момент и станут удовлетворять условию 1, обновляем ответ.
Оценка времени работы
Т.к. для каждого суффикса мы выполняем
операций, то итоговое время работыСм. также
- Построение суффиксного массива с помощью стандартных методов сортировки
- Алгоритм поиска подстроки в строке с помощью суффиксного массива
- Алгоритм Касаи и др.
Источники
- Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
- MAXimal :: algo :: Суффиксный массив
- Википедия — Суффиксный массив
- Wikipedia — Suffix array
- Habrahabr — Суффиксный массив — удобная замена суффиксного дерева