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

Коротко: Суффиксный массив — отсортированный список всех суффиксов текста. С ним любую подстроку можно найти двоичным поиском.

Подробнее: Для текста 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, обнаружение плагиата, полнотекстовые индексы.
• Сравнение: Для повторных поисков в одном тексте индекс окупается. Разовый поиск выполняют КМП или Бойер — Мур.

См. также: Инвертированный индекс