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

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

Внимание! Вы не авторизовались на сайте. Ваш 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>.}}
  
 
== Пример ==
 
== Пример ==
Строка 59: Строка 59:
 
{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}
 
{{main|Алгоритм поиска подстроки в строке с помощью суффиксного массива}}
  
=== Подсчёт LCP для лексикографически соседних суффиксов ===
+
=== Подсчет LCP для лексикографически соседних суффиксов ===
  
 
{{main|Алгоритм Касаи и др.}}
 
{{main|Алгоритм Касаи и др.}}
Строка 127: Строка 127:
 
# Возможны три случая:
 
# Возможны три случая:
 
#* <tex>|st| = lcp[s']</tex><br>Тогда просто обновляем <tex>i</tex> и <tex>j</tex> для вершины стека.
 
#* <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| \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>|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 + \mathrm{SA})</tex>, где <tex>\mathrm{SA}</tex> {{---}} время построения суффиксного массива.
  
 
==См. также==
 
==См. также==

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

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

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