Изменения
Нет описания правки
* Позволяет найти все вхождения образца <tex>p</tex> в строку <tex>s</tex> за время <tex>O(|p| + \log(|s|))</tex>
* Позволяет вычислить <tex>lcp</tex> (longest common prefix) для всех соседних в лексикографическом порядке суффиксов строки <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>.
==См. также==
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]
== Источники ==
* Дэн Гасфилд — Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология — СПб.: Невский Диалект; БХВ-Петербург, 2003. — 654 с: ил.
* [http://e-maxx.ru/algo/suffix_array MAXimal :: algo :: Суффиксный массив]
* [http://ru.wikipedia.org/wiki/Суффиксный_массив Википедия — Суффиксный массив]
* [http://en.wikipedia.org/wiki/Suffix_array Wikipedia — Suffix array]
* [http://habrahabr.ru/post/115346/ Habrahabr — Суффиксный массив — удобная замена суффиксного дерева]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Суффиксный массив]]
