Індекс підрядків

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

Деякі індекси підрядків:

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