Суффиксный массив — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
(доказательство, пример)
Строка 26: Строка 26:
 
=== Вариант для минимально возможного ===
 
=== Вариант для минимально возможного ===
 
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <tex>tmp</tex>, как в решении выше. Пусть, мы рассматриваем <tex>i</tex>-й в лексикографическом порядке суффикс (т.е. и <tex>i</tex>-й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если <tex>tmp[sa[i - 1] + 1] < tmp[sa[i] + 1]</tex>, т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.
 
Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку <tex>tmp</tex>, как в решении выше. Пусть, мы рассматриваем <tex>i</tex>-й в лексикографическом порядке суффикс (т.е. и <tex>i</tex>-й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если <tex>tmp[sa[i - 1] + 1] < tmp[sa[i] + 1]</tex>, т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.
 +
 +
==== Пример ====
 +
Дан суффиксный массив [7, 5, 1, 3, 6, 2, 4].
 +
[[Файл:ExampleSuffixArray.png]]
  
 
==== Псевдокод ====
 
==== Псевдокод ====
Строка 40: Строка 44:
 
         s[i] = alphabet[cur]       
 
         s[i] = alphabet[cur]       
 
   '''return''' s
 
   '''return''' s
 +
 +
==== Доказательство минимальности ====
 +
Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.
  
 
== Применения ==
 
== Применения ==

Версия 22:53, 10 июня 2015

Определение:
Cуффиксным массивом (англ. suffix array) строки [math]s[1 .. n][/math] называется массив [math]suf[/math] целых чисел от [math]1[/math] до [math]n[/math], такой, что суффикс [math]s[suf[i]..n][/math][math]i[/math]-й в лексикографическом порядке среди всех непустых суффиксов строки [math]s[/math].


Пример

[math]s = abacaba[/math]

SuffixArray.png

Значит, суффиксный массив для строки [math]s[/math] равен [math][7, 5, 1, 3, 6, 2, 4][/math].

Восстановление строки по суффиксному массиву

Задача:
Дан суффиксный массив некоторой строки [math]s[/math], необходимо восстановить строку за время [math]O(|s|)[/math].


Вариант для бесконечного алфавита

Так как наш алфавит не ограничен, можно [math]i[/math]-й в лексикографическом порядке суффикс сопоставить с [math]i[/math]-й буквой в алфавите.

Псевдокод

string fromSuffixArrayToString(int[] sa):
  for i = 1 to n
       s[sa[i]] = alphabet[i] 
  return s

Вариант для минимально возможного

Для начала вместо каждого символа строки поставим символ из бесконечного алфавита в промежуточную строку [math]tmp[/math], как в решении выше. Пусть, мы рассматриваем [math]i[/math]-й в лексикографическом порядке суффикс (т.е. и [math]i[/math]-й символ строки). Его первый символ будет равен первому символу предущего в лексикографическом порядке суффикса, если [math]tmp[sa[i - 1] + 1] \lt tmp[sa[i] + 1][/math], т.е. и их строки без первого символа так же в лексикографическом порядке. Иначе он должен быть больше, т.к. рассматриваемый суффикс следующий в лексикографическом порядке.

Пример

Дан суффиксный массив [7, 5, 1, 3, 6, 2, 4]. ExampleSuffixArray.png

Псевдокод

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

Доказательство минимальности

Докажем от противного. Пусть, есть решение в котором использовано меньше букв. Тогда найдется позиция в которой, наше решение отличается от минимального, причем в минимальном остается та же буква, как в предыдущем суффиксе, а в нашем появляется новая. Рассмотрим эти два подряд идущих суффикса. В решении выше добавится новая буква, только если продолжение первого суффикса лексикографически больше, чем продолжение второго. Получается, что в минимальном решении первый суффикс лексикографически больше, чем второй, что неверно. Пришли к противоречию.

Применения

  • Позволяет найти все вхождения образца [math]p[/math] в строку [math]s[/math] за время [math]O(|p| + \log(|s|))[/math].
  • Позволяет вычислить наибольший общий префикс (англ. longest common prefix, LCP) для всех соседних в лексикографическом порядке суффиксов строки [math]s[/math] за [math]O(|s|)[/math], то есть построить массив [math]LCP[1 .. |s| - 1][/math], где [math]LCP[i][/math] — длина наибольшего общего префикса суффиксов [math]s[suf[i] .. |s|][/math] и [math]s[suf[i + 1] .. |s|][/math].
  • Позволяет найти количество различных подстрок в строке за время [math]O(|s| \log(|s|))[/math] и [math]O(|s|)[/math] дополнительной памяти.
  • Позволяет найти наименьший циклический сдвиг строки за время [math]O(|s| \log(|s|))[/math].
  • Позволяет найти максимальную по длине строку, ветвящуюся влево и вправо за время [math]SA + O(n)[/math], где [math]SA[/math] — время построения суффиксного массива.

См. также

Источники