Редактирование: Построение суффиксного массива с помощью стандартных методов сортировки

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 65: Строка 65:
 
Рассмотрим теперь переход от префиксов длины <tex>l</tex> к префиксам длины <tex>2l</tex>. Научимся сравнивать два префикса длины <tex>2l</tex> за <tex>O(1)</tex>: Пусть даны префиксы <tex>s[i..i+2l-1]</tex>, <tex>s[j..j+2l-1]</tex>, сравним сначала их левые половинки, использовав значения <tex>c[i], c[j]</tex> с предыдущего шага, если <tex>c[i]\neq c[j]</tex>, то префиксы соотносятся так как же, как <tex>c[i]</tex> и <tex> c[j]</tex>, если <tex>c[i]=c[j]</tex>, то переходим к сравнению <tex>c[i+l]</tex> и <tex> c[j+l]</tex>. Итак, отсортировать префиксы длины <tex>2l</tex> можно за <tex>O(n\log n)</tex>. Вычислить новые <tex>c[i]</tex> можно просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая номер соответствующего класса на <tex>1</tex>, если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+l]</tex>).
 
Рассмотрим теперь переход от префиксов длины <tex>l</tex> к префиксам длины <tex>2l</tex>. Научимся сравнивать два префикса длины <tex>2l</tex> за <tex>O(1)</tex>: Пусть даны префиксы <tex>s[i..i+2l-1]</tex>, <tex>s[j..j+2l-1]</tex>, сравним сначала их левые половинки, использовав значения <tex>c[i], c[j]</tex> с предыдущего шага, если <tex>c[i]\neq c[j]</tex>, то префиксы соотносятся так как же, как <tex>c[i]</tex> и <tex> c[j]</tex>, если <tex>c[i]=c[j]</tex>, то переходим к сравнению <tex>c[i+l]</tex> и <tex> c[j+l]</tex>. Итак, отсортировать префиксы длины <tex>2l</tex> можно за <tex>O(n\log n)</tex>. Вычислить новые <tex>c[i]</tex> можно просто пробежавшись в лексикографическом порядке по префиксам, и увеличивая номер соответствующего класса на <tex>1</tex>, если текущий префикс не совпадает с предыдущим (сравнивать с помощью старых <tex>c[i], c[i+l]</tex>).
  
После шага <tex>l =2^{\lceil \log_2 n\rceil} \geqslant n</tex> все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log n)</tex>, каждый шаг проводится за <tex>O(n \log n)</tex>, итоговая асимптотика <tex>O(n \log^2 n)</tex>.
+
После шага <tex>l =2^{\lceil \log_2 n\rceil} \ge n</tex> все циклические сдвиги будут отсортированы. Всего шагов <tex>O(\log n)</tex>, каждый шаг проводится за <tex>O(n \log n)</tex>, итоговая асимптотика <tex>O(n \log^2 n)</tex>.
  
 
Схожая идея используется и в [[Алгоритм цифровой сортировки суффиксов циклической строки|алгоритме цифровой сортировки суффиксов циклической строки]], который имеет лучшую асимптотику.
 
Схожая идея используется и в [[Алгоритм цифровой сортировки суффиксов циклической строки|алгоритме цифровой сортировки суффиксов циклической строки]], который имеет лучшую асимптотику.

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

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

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

Шаблон, используемый на этой странице: