Суфіксний масив

Коротко: Суфіксний масив — відсортований список усіх суфіксів тексту. З ним будь-який підрядок можна знайти двійковим пошуком.

Докладніше: Для тексту banana суфікси — banana, anana, nana, ana, na, a. Зберігаються лише їхні початкові позиції в алфавітному порядку: [5, 3, 1, 0, 4, 2].

Подробиці

• Пошук: Шаблон довжини m знаходиться двійковим пошуком по суфіксах за O(m log n).
• Побудова: Наївно сортуванням за O(n² log n). Добрі алгоритми (SA-IS, подвоєння префікса) досягають O(n) — O(n log n).
• Порівняно із суфіксними деревами: Трохи повільніше, але набагато менше пам’яті.
• Доповнення — масив LCP: Зберігає довжину спільного префікса сусідніх суфіксів і дозволяє інші запити, наприклад найдовший повторюваний підрядок.
• Застосування: Біоінформатика (пошук по геному), перетворення Барроуза — Вілера в bzip2, виявлення плагіату, повнотекстові індекси.
• Порівняння: Для повторних пошуків в одному тексті індекс окупається. Одноразовий пошук виконують КМП чи Бойєр — Мур.

Див. також: Інвертований індекс