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

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

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

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