Суффиксные деревья

(суффиксные массивы suffix trees, suffix arrays, PATarrays); индекс, основанный на представлении всех значимых суффиксов текста в структуре данных, известной как бор (trie). Суффиксом в этом индексе называю любую «подстроку», начинающуюся с некоторой позиции текста (текст рассматривается как одна непрерывная строка) и продолжающуюся до его конца. В реальных приложениях длина суффиксов ограничена, а индексируются только значимые позиции – например, начала слов. Этот индекс позволяет выполнять более сложные запросы, чем индекс, построенный на инвертированных файлах.