Редактирование: Суффиксный массив

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|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>.}}
+
'''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>.}}
  
 
== Пример ==
 
== Пример ==
Строка 41: Строка 41:
 
         tmp[sa[i]] = alphabet[i]
 
         tmp[sa[i]] = alphabet[i]
 
   cur = 1
 
   cur = 1
   s[sa[1]] = alphabet[1]
+
   s[1] = alphabet[1]
 
   '''for''' i = 2 '''to''' n
 
   '''for''' i = 2 '''to''' n
 
         j = sa[i - 1]
 
         j = sa[i - 1]
Строка 47: Строка 47:
 
         '''if''' tmp[j + 1] > tmp[k + 1]  
 
         '''if''' tmp[j + 1] > tmp[k + 1]  
 
             cur++
 
             cur++
         s[sa[i]] = alphabet[cur]       
+
         s[i] = alphabet[cur]       
 
   '''return''' s
 
   '''return''' s
  
Строка 54: Строка 54:
  
 
== Применения ==
 
== Применения ==
 +
 +
Здесь и далее <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
  
 
=== Поиск подстроки в строке ===
 
=== Поиск подстроки в строке ===
Строка 59: Строка 61:
 
{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}
 
{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}
  
=== Подсчёт LCP для лексикографически соседних суффиксов ===
+
=== Подсчет LCP для лексикографически соседних суффиксов ===
  
 
{{main|Алгоритм Касаи и др.}}
 
{{main|Алгоритм Касаи и др.}}
Строка 65: Строка 67:
 
=== Число различных подстрок в строке ===
 
=== Число различных подстрок в строке ===
  
Вычисление числа различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти с использованием [[Алгоритм_Касаи_и_др.|LCP]]<ref name="ref1">[http://e-maxx.ru/algo/suffix_array#8 MAXimal :: algo :: Суффиксный массив :: Количество различных подстрок]</ref>.
+
Вычисление числа различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти с использованием [[Алгоритм_Касаи_и_др.|LCP]]<ref name="ref1">[http://e-maxx.ru/algo/suffix_array#8 Количество различных подстрок]</ref>.
  
 
=== Максимальная по длине ветвящаяся влево и вправо строка ===
 
=== Максимальная по длине ветвящаяся влево и вправо строка ===
Строка 84: Строка 86:
 
Будем говорить, что суффиксы <tex>i</tex> и <tex>j</tex> соответствуют строке <tex>s</tex>, если <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, а суффиксы <tex>i</tex> и <tex>j</tex> соответствуют позициям этих вхождений.
 
Будем говорить, что суффиксы <tex>i</tex> и <tex>j</tex> соответствуют строке <tex>s</tex>, если <tex>s</tex> входит в <tex>t</tex> дважды и не пересекаясь, а суффиксы <tex>i</tex> и <tex>j</tex> соответствуют позициям этих вхождений.
  
Для произвольной строки <tex>s</tex> и двух суффиксов, соответствующих ей, введем два условия:
+
Введем два условия:
 
# <tex>\max(|i|, |j|) \geqslant \min(|i|, |j|) + |s|</tex>
 
# <tex>\max(|i|, |j|) \geqslant \min(|i|, |j|) + |s|</tex>
 
# <tex>|s| = \min\limits_{k=i'\dots j'}lcp[k]</tex>
 
# <tex>|s| = \min\limits_{k=i'\dots j'}lcp[k]</tex>
Строка 113: Строка 115:
 
# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
 
# Переберем все пары <tex>i</tex> и <tex>j</tex> такие, что они удовлетворяют условиям 1 и 2 и возьмем среди них максимум по длине строки.
  
Этот алгоритм можно реализовать за <tex>O(n^3 + \mathrm{SA})</tex> или за <tex>O(n^2 + \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
+
Этот алгоритм можно реализовать за <tex>O(n^3)</tex> или за <tex>O(n^2)</tex>.
  
 
==== Оптимальное решение ====
 
==== Оптимальное решение ====
 
===== Идея =====
 
===== Идея =====
Будем перебирать всевозможные подстроки <tex>s</tex> строки <tex>t</tex> такие, что они входят в <tex>t</tex> дважды и удовлетворяют условию 2 при любых <tex>i</tex> и <tex>j</tex>, где <tex>i</tex> и <tex>j</tex> {{---}} суффиксы, соответствующие двум любым вхождениям <tex>s</tex> в <tex>t</tex> (т.е. не обязательно непересекающимся). Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1.  
+
Будем перебирать всевозможные подстроки <tex>s</tex> строки <tex>t</tex> такие, что они входят в <tex>t</tex> дважды и удовлетворяют условию 2 при любых <tex>i</tex> и <tex>j</tex>, где <tex>i</tex> и <tex>j</tex> {{---}} суффиксы, соответствующие двум любым вхождениям <tex>s</tex> в <tex>t</tex> (т.е. не обязательно непересекающимся).Для каждой такой строки <tex>s</tex> попробуем найти <tex>i</tex> и <tex>j</tex>, удовлетворяющие условию 1.  
 
Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
 
Таким образом, мы рассмотрим все строки, соответствующие условиям 1 и 2, и, следовательно, найдем ответ. Алгоритм корректный.
  
Строка 126: Строка 128:
 
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>k</tex> длины <tex>lcp[k']</tex> (т.е. строки <tex>s</tex>) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>i</tex> и максимальный по длине <tex>j</tex>. Обозначим за <tex>st</tex> вершину стека, а за <tex>s</tex> {{---}} текущий рассматриваемый суффикс.
 
# Будем идти по суффиксному массиву в порядке лексикографической сортировки суффиксов. В стеке будем хранить префиксы уже рассмотренных суффиксов <tex>k</tex> длины <tex>lcp[k']</tex> (т.е. строки <tex>s</tex>) в порядке увеличения длины. Для каждой строки из стека также будем хранить минимальный по длине суффикс <tex>i</tex> и максимальный по длине <tex>j</tex>. Обозначим за <tex>st</tex> вершину стека, а за <tex>s</tex> {{---}} текущий рассматриваемый суффикс.
 
# Возможны три случая:
 
# Возможны три случая:
#* <tex>|st| = lcp[s']</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.
+
#* <tex>lcp[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>lcp[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>lcp[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>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> {{---}} время построения суффиксного массива.
+
Т.к. построение суффиксного массива и подсчет <tex>lcp</tex> выполняется за <tex>O(n)</tex> и для каждого суффикса мы выполняем <tex>O(1)</tex> операций, то итоговое время работы <tex>O(n)</tex>.
  
 
==См. также==
 
==См. также==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)