Суфіксний масив — це лексикографічно відсортований масив усіх суфіксів рядка. Цю структуру даних розробили Юджин Майєрс і Уді Манбер як більш економну з погляду використання пам'яті альтернативу суфіксному дереву.
Приклад Побудуємо суфіксний масив для рядка «abracadabra» довжини 11 символів.
a b r a c a d a b r a 1 2 3 4 5 6 7 8 9 10 11
Випишемо всі його суфікси (з вказанням їх початку): 1 — abracadabra 2 — bracadabra 3 — racadabra 4 — acadabra 5 — cadabra 6 — аdabra 7 — dabra 8 — abra 9 — bra 10 — ra 11 — a
Відсортуємо суфікси лексикографічно: 11 — a 8 — abra 1 — abracadabra 4 — acadabra 6 — adabra 9 — bra 2 — bracadabra 5 — cadabra 7 — dabra 10 — ra 3 — racadabra
Суфіксним масивом цього рядка буде — {11,8,1,4,6,9,2,5,7,10,3}, що складається з індексів початків суфіксів відсортованих лексикографічно.
Зв'язок із суфіксними деревами Суфіксний масив може бути побудований обходом у глибину суфіксного дерева.
Див. також Перетворення Берроуза — Вілера FM-індекс
Посилання