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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Применения)
(Применения)
Строка 11: Строка 11:
  
 
== Применения ==
 
== Применения ==
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| \log(|s|))</tex>
+
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + \log(|s|))</tex>
 
* Позволяет вычислить наибольший общий префикс (англ. ''longest common prefix'', ''LCP'') для всех соседних в лексикографическом порядке суффиксов строки <tex>s</tex> за <tex>O(|s|)</tex>, то есть построить массив <tex>LCP[1 .. |s| - 1]</tex>, где <tex>LCP[i]</tex> {{---}} длина наибольшего общего префикса суффиксов <tex>s[suf[i] .. |s|]</tex> и <tex>s[suf[i + 1] .. |s|]</tex>.
 
* Позволяет вычислить наибольший общий префикс (англ. ''longest common prefix'', ''LCP'') для всех соседних в лексикографическом порядке суффиксов строки <tex>s</tex> за <tex>O(|s|)</tex>, то есть построить массив <tex>LCP[1 .. |s| - 1]</tex>, где <tex>LCP[i]</tex> {{---}} длина наибольшего общего префикса суффиксов <tex>s[suf[i] .. |s|]</tex> и <tex>s[suf[i + 1] .. |s|]</tex>.
 
* Позволяет найти количество различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти.
 
* Позволяет найти количество различных подстрок в строке за время <tex>O(|s| \log(|s|))</tex> и <tex>O(|s|)</tex> дополнительной памяти.

Версия 07:30, 24 марта 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]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].

См. также

Источники