Суффиксный массив — различия между версиями
(→Добавлено применение и переоформлены старые) |
(→Применения) |
||
Строка 59: | Строка 59: | ||
=== Поиск подстроки в строке === | === Поиск подстроки в строке === | ||
− | |||
[[Алгоритм_поиска_подстроки_в_строке_с_помощью_суффиксного_массива|Основная статья]] | [[Алгоритм_поиска_подстроки_в_строке_с_помощью_суффиксного_массива|Основная статья]] | ||
=== Подсчет LCP соседних лексикографически суффиксов === | === Подсчет LCP соседних лексикографически суффиксов === | ||
− | + | [[Алгоритм_Касаи_и_др.|Основная статья]] | |
=== Количество различных подстрок в строке === | === Количество различных подстрок в строке === | ||
Строка 72: | Строка 71: | ||
=== Наименьший циклический сдвиг строки === | === Наименьший циклический сдвиг строки === | ||
− | |||
[[Декомпозиция_Линдона#Поиск лексикографически минимального суффикса строки|Основная статья]] | [[Декомпозиция_Линдона#Поиск лексикографически минимального суффикса строки|Основная статья]] | ||
Версия 15:07, 5 июня 2016
Определение: |
Cуффиксным массивом (англ. suffix array) строки | называется массив целых чисел от до , такой, что суффикс — -й в лексикографическом порядке среди всех непустых суффиксов строки .
Содержание
- 1 Пример
- 2 Восстановление строки по суффиксному массиву
- 3 Применения
- 3.1 Поиск подстроки в строке
- 3.2 Подсчет LCP соседних лексикографически суффиксов
- 3.3 Количество различных подстрок в строке
- 3.4 Наименьший циклический сдвиг строки
- 3.5 Максимальная по длине ветвящаяся влево и вправо строка
- 3.6 Самая длинная строка [math]p[/math], входящая в [math]t[/math] дважды и не пересекаясь
- 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 и 2, то она входит в дважды и не пересекаясь. |
proof |
Утверждение: |
Если строка входит в дважды и не пересекаясь, то соответствующие ей суффиксы и удовлетворяют условиям 1 и 2. |
proof |
Т.о. строка входит в дважды и не пересекаясь тогда и только тогда, когда она удовлетворяет условиям 1 и 2.
Тогда на ум приходит следующий наивный алгоритм:
- Построим суффиксный массив, посчитаем на нём LCP.
- Переберем все пары и такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
Этот алгоритм можно реализовать за
или, если немного подумать, то и за . Однако, он не позволяет достигнуть нужной нам асимптотики.
Чтобы достигнуть асимптотики , будем перебирать всевозможные подстроки строки , такие, что они входят в дважды и являются максимальными в том смысле, что удовлетворяет условию 2 при любых и , где и - суффиксы, соответствующие двум любым вхождениям s в t (т.е. не обязательно непересекающимся). Для каждой такой строки попробуем найти и , удовлетворяющие условию 1. Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
Заметим теперь, что искомые строки
— это префиксы суффиксов длины . Для того, чтобы найти для каждой такой строки суффиксы и , удовлетворяющие условию 1, воспользуемся стеком. Алгоритм следующий:- Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов длины (т.е. строки ) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс и максимальный по длине . Обозначим за вершину стека, а за — текущий рассматриваемый суффикс.
- Возможны три случая:
- . Тогда просто обновляем и для вершины стека: if ( ) then ;
- . Тогда добавляем новую вершину в стек и обновляем для нее и :
- . Достаем вершину из стека и "пробрасываем" значения и из нее в новую вершину стека. Это нужно для того, чтобы не потерять значения и , которые были посчитаны для строк большей длины, но так же актуальны для строк меньшей длины.
- Если в какой-то момент и станут удовлетворять условию 1, обновляем ответ: if ( ) then ;
Т.к. для каждого суффикса мы выполняем
операций, то итоговое время работыСм. также
- Построение суффиксного массива с помощью стандартных методов сортировки
- Алгоритм поиска подстроки в строке с помощью суффиксного массива
- Алгоритм Касаи и др.
Источники
- Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
- MAXimal :: algo :: Суффиксный массив
- Википедия — Суффиксный массив
- Wikipedia — Suffix array
- Habrahabr — Суффиксный массив — удобная замена суффиксного дерева