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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
<tex>i</tex>-ым суффиксом строки <tex>s[1 .. n]</tex> называется подстрока <tex>s[i .. n]</tex>, <tex>i = 1 .. n</tex>.
 
<tex>i</tex>-ым суффиксом строки <tex>s[1 .. n]</tex> называется подстрока <tex>s[i .. n]</tex>, <tex>i = 1 .. n</tex>.
 
}}
 
}}
 +
 +
{{Определение
 +
|definition=
 +
'''Cуффиксным массивом''' строки <tex>s[1 .. n]</tex> называется перестановка индексов суффиксов <tex>i = 1 .. n</tex>, которая упорядочивает суффиксы в лексикографическом порядке.
 +
}}
 +
 
Суффиксный массив для строки <tex>s</tex> может быть построен за <tex>O(|s|)</tex>.
 
Суффиксный массив для строки <tex>s</tex> может быть построен за <tex>O(|s|)</tex>.
  

Версия 13:24, 9 июня 2012

Определение:
[math]i[/math]-ым суффиксом строки [math]s[1 .. n][/math] называется подстрока [math]s[i .. n][/math], [math]i = 1 .. n[/math].


Определение:
Cуффиксным массивом строки [math]s[1 .. n][/math] называется перестановка индексов суффиксов [math]i = 1 .. n[/math], которая упорядочивает суффиксы в лексикографическом порядке.


Суффиксный массив для строки [math]s[/math] может быть построен за [math]O(|s|)[/math].

Пример

[math]s = abacaba[/math]. Суффиксы [math]s[/math] в лексикографическом порядке:
1) [math]a[/math]
2) [math]aba[/math]
3) [math]abacaba[/math]
4) [math]acaba[/math]
5) [math]ba[/math]
6) [math]bacaba[/math]
7) [math]caba[/math]
Значит суффиксный массив для строки [math]s[/math] равен [math]suf = \{7, 5, 1, 3, 6, 2, 4\}[/math]

Применения

  • Позволяет найти все вхождения образца [math]p[/math] в строку [math]s[/math] за время [math]O(|p| + \log(|s|))[/math]
  • Позволяет вычислить [math]lcp[/math] (longest common prefix) для всех соседних в лексикографическом порядке суффиксов строки [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].

Литература

  • Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.

См. также