Индекс подстрок

Индекс подстрок — это структура данных, позволяющая производить поиск подстроки в тексте или наборе текстов за сублинейное время. Это значит, что имея документ $S$ длины $n$ или набор документов $D=\{S^{1},S^{2},\dots ,S^{d}\}$ общей длины $n$, вы можете найти все вхождения образца $P$ за $o(n)$ (См. O-нотация). Словосочетание полнотекстовый индекс также иногда используется для обозначения индекса всех подстрок текста, но является неоднозначным, так как также используется для обозначения обычных индексов слов, например, инвертированного индекса.

Некоторые индексы подстрок:

• Суффиксный автомат
• Суффиксное дерево
• Суффиксный массив
• Индекс N-грамм
• FM-индекс
• LZ-индекс