Индекс подстрок — структура данных, позволяющая производить поиск подстроки в тексте или наборе текстов за сублинейное время. Это значит, что имея документ длины или набор документов общей длины , вы можете найти все вхождения образца за (в o-нотации). Термин полнотекстовый индекс также иногда используется для обозначения индекса всех подстрок текста, но является неоднозначным, так как также используется для обозначения обычных индексов слов, например, инвертированного индекса и иногда используется в широком смысле для любой хранимой структуры, предназначенной для задач полнотекстового поиска.
Некоторые индексы подстрок: суффиксный автомат, суффиксное дерево, суффиксный массив, индекс N-грамм, , LZ-индекс.
Литература
Категория:Строковые алгоритмы Категория:Техники индексации данных