Суффиксный массив — лексикографически отсортированный массив всех суффиксов строки. Эта структура данных была разработана Джином Майерсом и Уди Манбером как более экономная альтернатива суффиксному дереву с точки зрения необходимой памяти. Она часто применяется там, где необходим быстрый поиск подстрок, например в преобразовании Барроуза — Уилера (BWT), а также в качестве структуры данных в поисковом индексе.
Рассмотрим строку «abracadabra» длиной 11 символов.
a b r a c a d a b r a 1 2 3 4 5 6 7 8 9 10 11
Отсортированный список её суффиксов:
a abra abracadabra acadabra adabra bra bracadabra cadabra dabra ra racadabra
Суффиксный массив этой строки — {11,8,1,4,6,9,2,5,7,10,3}, потому что суффикс «a» начинается с 11-го знака, суффикс «abra» — с 8-го, и так далее, вплоть до последнего суффикса «racadabra», который начинается с третьего символа исходного слова.
Теперь с помощью этого массива можно легко найти все подстроки. Например, если нужно найти подстроку «ab», достаточно найти все суффиксы, которые начинаются на «ab». За счёт сортировки по алфавиту, они находятся рядом друг с другом. Используя бинарный поиск, мы находим 2-й и 3-й суффиксы «abra» и «abracadabra», которым соответствуют 2-й и 3-й элемент суффиксного массива (8 и 1). Это означает, что искомая подстрока «ab» встречается на первом и восьмом символе в исходном слове.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .