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

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

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