Суффиксный массив

Определение:

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

Пример

$s = abacaba$

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

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

Задача:

Дан суффиксный массив некоторой строки $s$, необходимо восстановить строку за время $O(|s|)$.

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

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

Псевдокод

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

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

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

Псевдокод

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

Применения

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

См. также

• Построение суффиксного массива с помощью стандартных методов сортировки
• Алгоритм поиска подстроки в строке с помощью суффиксного массива
• Алгоритм Касаи и др.

Источники

• Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
• MAXimal :: algo :: Суффиксный массив
• Википедия — Суффиксный массив
• Wikipedia — Suffix array
• Habrahabr — Суффиксный массив — удобная замена суффиксного дерева